Measuring the Median

Meteorology mainly uses the median as its representative value. The hint defines the median.

A machine reads the temperature once per second, and it needs software. The machine has one small digital display, and every second that display shows the median of the temperatures measured during the last $K$ seconds.

The software is tested on a computer first, before it is loaded onto the machine.

Given the temperatures measured over $N$ seconds, write a program that computes the sum of the medians shown on the display. In other words, given $N$ numbers, compute the sum of the medians of the $N-K+1$ contiguous subsequences of length $K$.

The first line contains $N$ and $K$. ($1 \le N \le 250000$, $1 \le K \le 5000$, $K \le N$)

Each of the next $N$ lines contains one measured temperature, given in order. A temperature is an integer between $0$ and $65535$, inclusive.

Print the sum of the medians of all $N-K+1$ contiguous subsequences of length $K$.

The median of $K$ numbers is the $\lfloor (K+1)/2 \rfloor$-th smallest of them. Counting starts at 1, and the added 1 makes the index land exactly in the middle when $K$ is odd.

For example, the median of $(1, 2, 6, 5, 4, 3)$ is $3$, and the median of $(11, 13, 12, 14, 15)$ is $13$.