Alice is going trick-or-treating! Her goal is to visit every house in her neighborhood before they turn off their lights. Alice's neighborhood is represented by an one-dimensional array, with the i-th element representing the amount of minutes before the i-th house turns off its lights. Every minute, Alice can go one house to the left, or one house to the right. If Alice arrives at the moment a house turns its lights off, they will not give her candy. Alice needs you to help her find out if she can visit every house before they turn their lights off. If she can, find the minimum amount of time it would take her. Else, output -1.
The first line of each test cases contains integer $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 2000, 1 \leq k \leq n$$$), the size of the array and Alice's position in the array (1-indexed).
The second line contains $$$n$$$ integers $$$a_1, a_2,...,a_n\ (1 \leq a_i \leq 10^6)$$$, the elements of the array.
For each test case, output the minimum time it would take Alice to visit every house and still collect candy from them. If this is not possible, output -1.
5 25 1 2 9 8
7
5 3100 3 1 5 6
8
5 22 1 4 5 5
-1
It can be shown that Alice cannot visit all of the houses in time in third test case.
