409492: GYM103584 E Truffula Trouble

The Once-ler is back with his lucrative Thneed business!

There are $$$N$$$ truffula trees in a row, and the Once-ler visits them in order, starting at the first truffula tree. He starts with a Super-Axe-Hacker with durability $$$d$$$.

Each truffula tree has toughness $$$t_i$$$, and the Once-ler can choose to chop down a truffula tree if and only if the durability of his Super-Axe-Hacker is greater than or equal to the current tree's toughness ($$$d \ge t_i$$$). Every time the Once-ler chops down a tree, the durability of his Super-Axe-Hacker decreases by one.

However, this time, the Once-ler wants to avoid chopping down trees unsustainably and angering the Lorax. Therefore, the Once-ler refuses to chop down more than one tree in a row.

However, he still needs to make a profit. Each truffula tree he cuts down can make one Thneed. To reach his quota, he needs to make $$$k$$$ Thneeds.

What is the minimum starting durability $$$d_{min}$$$ of the Once-ler's Super-Axe-Hacker that guarantees at least $$$k$$$ Thneeds will be made?

The first line contains two integers $$$N$$$ and $$$k$$$ where $$$N$$$ is the number of truffula trees, and $$$k$$$ is the number of Thneeds the Once-ler needs to make. ($$$1 \le N \le 10^5, 1 \le k \le N$$$)

The next line contains $$$N$$$ integers $$$t_1...t_n$$$ where $$$t_i$$$ is the toughness of the $$$i$$$th truffula tree. ($$$1 \le t_i \le 10^9$$$)

Output $$$d_{min}$$$, the minimum starting durability that guarantees at least $$$k$$$ Thneeds will be made. If it is not possible to make $$$k$$$ Thneeds while satisfying all the requirements, output $$$-1$$$.

6 2
4 9 2 1 2 10

3

6 5
8 8 8 8 8 8

-1

In the first example, the Once-ler starts with durability $$$d=3$$$, and chops down the 3rd and 5th trees to create 2 Thneeds.

In the second example, the Once-ler cannot make 5 Thneeds without angering the Lorax.