Median

The median of a sequence is the value at position (length + 1) / 2 after sorting it in nondecreasing order, using integer division for the position. For length 6 this is the 3rd value, and for length 5 it is also the 3rd value.

You are given N temperature readings, one per second. Starting when at least K readings have been measured, the display shows the median of the most recent K readings at each second.

For the length-N sequence, compute the median of every contiguous subsequence of length K and output the sum of those medians.

The first line contains two integers N and K. N is a positive integer at most 250,000, K is a positive integer at most 5,000, and K ≤ N always holds.

Each of the next N lines contains one temperature value. Every value is an integer between 0 and 65,536, inclusive.

Output, on the first line, the sum of the medians of all contiguous subsequences of length K. The answer is at most 2^63 - 1.