A monitor keeps a sliding window of the last w latency readings. For every contiguous window of exactly w consecutive readings (there are n - w + 1 of them, left to right), report the window's lower median: sort the window ascending as v[0] <= ... <= v[w-1] and take the element at 0-based index (w - 1) // 2.
Input format
Line 1: two integers n and w.
Line 2: n space-separated integers, the readings in order.
Output format
n - w + 1 space-separated integers on one line: the lower median of each window, left to right.
Constraints
- 1 <= w <= n <= 100000
- -1000000000 <= each reading <= 1000000000