14271427 SUSTech Online Judge
Problem 1427 --Median II

1427: Median II

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 151  Solved: 33
[Submit][Status][Web Board]


Given an array \(a\) of length \(n\). You need to find a subarray \(a[l..r]\) with length at least \(k\) with the \(largest\) median.

A median in an array of length \(x\) is the \(⌊(x+1)/2⌋-th\) smallest element of it. For example: median([1,2,3,4])=2, median([3,2,1])=2, median([2,1,2,1])=1.

Subarray \(a[l..r]\) is a sub-array \(a\), it includes \(a_l, a_{l+1} ... a_r\) for \(1≤l≤r≤n\), its length is \(r−l+1\).


The 1st line contains two integers \(n\) and \(k (1⩽  k ⩽ n ⩽  200000)\)

The 2nd line has \(n\) integers: \(a_1, a_2 ... a_n\). For each \(a_i(0⩽ a_i ⩽ 10^9)\)


Output one integer \(m\) — the maximum median you can get.

Sample Input

5 3
1 2 3 2 1

Sample Output



The max median 2 is found from [2 3 2]