Problem C
Jumping Jack

For as long as he could remember, Jack has loved to jump. His goal is to become an Olympic athlete someday, so he spends lots of time practicing his jumping skills. Jack has set up a course of checkpoints along a straight line from his starting point. To go through this course, Jack picks a jumping level, which defines how far he can travel along these checkpoints. Specifically, if Jack is at a checkpoint located at position $i$ and has picked jumping level $j$, he will jump to the furthest checkpoint that is at or before position $i + j$. If there is no checkpoint in the range $[i + 1, i + j]$, then Jack will fail to finish the course because he cannot make a jump.

Jack wants to know how he should pick his jumping level so that he can make it through the course. Additionally, in order to get in enough practice without overexercising, Jack wants to finish the course in exactly $k$ jumps. Given the positions of all the checkpoints, find the maximum jump level that Jack should pick to make it through the course with exactly $k$ jumps or determine if it is impossible to do so.

Input

The first line of input is $2$ integers separated by spaces $n$ and $k$ such that $3 \leq n \leq 10^6$ and $2 \leq k < n$. The next line is $n$ distinct integers in sorted order that represent the checkpoint positions, $c_ i$, that Jack jumps to. You are guaranteed that $c_1 = 0$ and $c_ i \leq 10^6$

Output

Output a single integer representing the maximum possible jump size such that Jack takes exactly $k$ jumps through the checkpoints given that jump size. If no such jump size exists, output $-1$.

5 4
0 2 4 6 7

2

5 4
0 1 2 3 30

-1