As per usual UCF is working on expanding the outside eating location outside the Student Union. They

Fantastic news! We've Found the answer you've been seeking!

Question:

As per usual UCF is working on expanding the outside eating location outside the Student Union. They have set up chairs on a linear path that extends quite far. To prevent the engineering students from constructing towers from the chairs the SGA has supplied chairs that arc bolted to the ground and can no longer be moved. The only issue is that the sun is overbearing and the rain can ruin the outside lunches during the summer. UCF bought k parasol stands to help cover the outside seating. However, UCF has not purchased any parasol tops nor has determined where to place the parasols. UCF has hired you to help protect their students from the weather. They want to buy k identical parasol tops to cover all the seating. Path chair should be completely covered by at least one parasol. UCF does not want to spend too much money, so you will help determine the minimum integral width of the parasol heads such that all the chairs can be covered.

Suppose you have 2 parasols stands, and 4 chain at positions 1, 4, 7, and I I. We could cover all the chairs with parasol widths of 6. See the following diagram,

However, we could also cover all the chairs with parasol widths of 5, See the following diagram.

You can find out that regardless of placement it is not possible to cover all chairs using 2 parasols with widths less than 5.

Input Specification

The first line of input contains a two positive integers, n and k, (n, k ? 200,000) representing the number of chairs and the number of parasol stands. The following line will contain n positive, space separated integers representing the position of the chairs in meters from the student union.

Note that each chair?s position will be given in increasing order.