Construction
Output: Standard Output (stdout)
Memory limit: 10 megabytes
Time limit: 10.0 seconds
Brenda the Builder specializes in building twodimensional apartment blocks in mountainous areas. However, she is always looking for ways to cut costs.
Before starting to build, Brenda must first level the ground to create the foundation for her building. Brenda has access to a strip of land of length N with varying heights, modelled as a series of integer height blocks H_0, H_1, ..., H_{N1}. She would like to level K contiguous blocks of land to create a foundation. The cost of building the foundation is equal to the height of the highest block to be levelled minus the height of the lowest block to be levelled.
Your job is to help Brenda by computing the lowest possible cost of building her foundation.
Input
The input consists of two lines.
The first line will contain two positive integers N and K, representing the number of land blocks and the length of the foundation. It is guaranteed that K \leq N.
The second line will contain N spaceseparated integers H_i, representing the height of the land for that block. It is guaranteed that 0 \leq H_i \leq 10^9.
Output
The output should be a single integer: the lowest possible cost for Brenda's foundation.
Note: Python submissions could take as much as 40 seconds to process so submitting too frequently will clog up our server.
Subtasks
 Subtask 1 (45%): N \leq 1,000
 Subtask 2 (40%): N \leq 100,000
 Subtask 3 (15%): N \leq 300,000
For Subtask 3, you need to think of a faster algorithm you could use.

Sample Input 1
3 2 4 1 2
Sample Output 1
1