Max Median

time limit per test 2 seconds

memory limit test 256 megabytes

Articles

You are a given an array $a$ of length $n$. Find a subarray $a[l..r]$ with length at least $k$ with the largest median.

A median in an array of length $n$ is an element which occupies position number $⌊ \frac {n+1}{2}⌋$ after we sort the elements in non-decreasing order. 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 contiguous part of the array $a$, $i. e.$ the array $a_l,a_{l+1},…,a_r$for some $1≤l≤r≤n$, its length is $r−l+1$.

Input

The first line contains two integers $n$ and $k$ ($1≤k≤n≤2⋅10^5$).

The second line contains $n$ integers $a_1,a_2,…,a_n$ ($1≤ai≤n$).

Output

Output one integer $m$ — the maximum median you can get.

Example

input

5 3
1 2 3 2 1

output

2

input

4 2
1 2 3 4

output

3

Note
In the first example all the possible subarrays are $[1..3], [1..4], [1..5], [2..4], [2..5]$ and $[3..5]$ and the median for all of them is $2$, so the maximum possible median is $2$ too.

In the second example $median([3..4])=3$.

思路

首先二分一个中位数 $x$，然后思考一个区间 $[l,r]$ 的中位数不小于 $x$ 要满足什么条件？

记录一个前缀数组 $p[i]$ 表示在前 $i$ 个元素中小于 $x$ 的个数，所以若 $r-(l-1) > 2*(p[r] - p[l-1])$ ，则该区间 $[l,r]$ 中位数不小于 $x$。

最后从一个区间 $[l, r]$ 推到所有区间，即所有满足 $r-2*p[r] > (l-1) - 2*p[l-1]$ 关系的区间，它们的中位数都不小于 $x$。

由于频繁的插入和前缀求和，所以我们选择树状数组进行优化。

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e6+1;
int n, k, a[maxn], b[maxn], c[maxn];
int tree[maxn];

void add(int x) {
    for(int i = x; i <= 2*n; i += i&-i) {
        tree[i] ++;
    }
}

int sum(int x) {
    int ans = 0;
    for(int i = x; i; i -= i&-i) {
        ans += tree[i];
    }
    return ans;
}

bool check(int x) {
    for(int i = 1; i <= 2*n; ++ i) tree[i] = 0;
    c[0] = n+1;
    for(int i = 1; i <= n; ++ i) {
        b[i] = b[i-1] + (a[i] < x);
        c[i] = i - 2*b[i] + n+1;
        if (i >= k) add(c[i-k]);
        if (sum(c[i]-1)) return true;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k;
    for(int i = 1; i <= n; ++ i) {
        cin >> a[i];
    }
    int l = 1, r = n+1;
    while(l < r) {
        int mid = (l+r) >> 1;
        if (check(mid)) l = mid+1;
        else r = mid;
    }
    cout << l-1 << "\n";
    return 0;
}