Remove Trees

Time Limit: 3000 ms Memory Limit: 65536 KiB

Problem Description

Shandong University of Science and Technology grove is a place frequented by lovers, there is a small drain fir trees grow particularly close, it\'s a good line of sight blocked. Assuming a row of trees with n trees, the headmaster allow us only cut m trees (except the first and the last tree), your task is to be calculated after cut m trees, the maximum of the shortest distance of remaining trees that is adjacent.

Input

There are multiple test cases.
For each case:
Line 1: Three space-separated integers: n, and m(2<=m,n<=50000,m<=n-2)
Lines 2..N+1: Each line contains a single integer l(0<=l<=1000000000) indicating how far the tree is away from the starting tree. No two rocks share the same position.

Output

Line 1: A single integer that is the maximum of the shortest distance.

Sample Input

7 2
0
11
2
14
21
17
25

Sample Output

4

Hint

 

Source

SDUST