E. Mountain Ranges
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are looking out the window and see n mountains, where the height of the i-th mountain is hi.

You consider that two neighboring mountains i and (i + 1) belong to the same mountain range if |hi - hi + 1| ≤ k, where k is the similarity parameter.

Determine the minimum possible similarity parameter k such that all mountains are divided into exactly m mountain ranges.

Input

The first line contains two integers n and m (1 ≤ m ≤ n ≤ 2·105) — the number of mountains and the required number of mountain ranges.

The second line contains n integers h1, h2, ..., hn (1 ≤ hj ≤ 106,  j = 1, 2, ..., n) — the height of the j-th mountain.

Output

In a single line, output a single positive integer k — the similarity parameter at which all mountains are divided into exactly m mountain chains.

If there are multiple possible values of k, output the minimum value.

If no solution exists, output  - 1 as the answer.

Examples
Input
11 3
2 3 1 5 2 1 4 8 7 9 6
Output
3
Input
5 3
3 1 5 7 6
Output
-1
Note

First test example

With k = 3, the following m = 3 mountain ranges are formed:

  • 1... 3: |2 - 3| ≤ 3, |3 - 1| ≤ 3, |1 - 5| > 3;
  • 4... 7: |5 - 2| ≤ 3, |2 - 1| ≤ 3, |1 - 4| ≤ 3, |4 - 8| > 3;
  • 8... 11: |8 - 7| ≤ 3, |7 - 9| ≤ 3, |9 - 6| ≤ 3.

With k = 2, there will be 6 mountain ranges.

Second test example

With k = 2, the following 2 mountain ranges are formed:

  • 1... 2: |3 - 1| ≤ 2, |1 - 5| > 2;
  • 3... 5: |5 - 7| ≤ 2, |7 - 6| ≤ 2.

With k = 1, there will be 4 mountain ranges.

It is clear that there is no k such that exactly m = 3 mountain ranges are formed.