#include<bits/stdc++.h>
#define lowbit(x) ((x)&(-(x)))
#define LL long long
using namespace std;
const int maxn = 1e5+10;
int cnt[maxn<<2];
int n,a[maxn],m;
LL sum;
void ins(int t){while (t<=m) {cnt[t]++; t += lowbit(t);}}
int getsum(int t){
    int ans = 0;
    while (t) {ans += cnt[t]; t -= lowbit(t);}
    return ans;
}
bool check(int t){
    memset(cnt,0,sizeof(cnt));
    int now = 0;
    LL ans = 0;
    ins(now + n);
    for (int i=0;i<n;i++) {
        if(a[i] >= t){
            ans += getsum(now+1+n);
            now++;
            ins(now+n);
        }else{
            ans += getsum(now-1+n);
            now--;
            ins(now+n);
        }
    }
    return ans >= sum - ans;
}

void work(){
    m = (n << 1) + 1;
    int l = 1e9+10, r = 0;
    for (int i=0;i<n;i++){
        scanf("%d",&a[i]);
        if (a[i] < l) l = a[i];
        if (a[i] > r) r = a[i];
    }
    sum = 1LL * n * (n - 1) / 2 + n;
    int ans = -1,mid;
    while (l<=r){
        mid = (l+r)>>1;
        if (check(mid)) {
            ans = mid, l = mid + 1;
        }else {
            r = mid - 1;
        }
    }
    printf("%d\n",ans);
}
int main(){
    while (~scanf("%d",&n)) work();
    return 0;
}



### Prompt

Please provide a cpp coded solution to the problem described below:

We will define the median of a sequence b of length M, as follows:

* Let b' be the sequence obtained by sorting b in non-decreasing order. Then, the value of the (M / 2 + 1)-th element of b' is the median of b. Here, / is integer division, rounding down.



For example, the median of (10, 30, 20) is 20; the median of (10, 30, 20, 40) is 30; the median of (10, 10, 10, 20, 30) is 10.

Snuke comes up with the following problem.

You are given a sequence a of length N. For each pair (l, r) (1 \leq l \leq r \leq N), let m_{l, r} be the median of the contiguous subsequence (a_l, a_{l + 1}, ..., a_r) of a. We will list m_{l, r} for all pairs (l, r) to create a new sequence m. Find the median of m.

Constraints

* 1 \leq N \leq 10^5
* a_i is an integer.
* 1 \leq a_i \leq 10^9

Input

Input is given from Standard Input in the following format:


N
a_1 a_2 ... a_N


Output

Print the median of m.

Examples

Input

3
10 30 20


Output

30


Input

1
10


Output

10


Input

10
5 9 5 9 8 9 3 5 4 3


Output

8

### Response

```cpp
#include<bits/stdc++.h>
#define lowbit(x) ((x)&(-(x)))
#define LL long long
using namespace std;
const int maxn = 1e5+10;
int cnt[maxn<<2];
int n,a[maxn],m;
LL sum;
void ins(int t){while (t<=m) {cnt[t]++; t += lowbit(t);}}
int getsum(int t){
    int ans = 0;
    while (t) {ans += cnt[t]; t -= lowbit(t);}
    return ans;
}
bool check(int t){
    memset(cnt,0,sizeof(cnt));
    int now = 0;
    LL ans = 0;
    ins(now + n);
    for (int i=0;i<n;i++) {
        if(a[i] >= t){
            ans += getsum(now+1+n);
            now++;
            ins(now+n);
        }else{
            ans += getsum(now-1+n);
            now--;
            ins(now+n);
        }
    }
    return ans >= sum - ans;
}

void work(){
    m = (n << 1) + 1;
    int l = 1e9+10, r = 0;
    for (int i=0;i<n;i++){
        scanf("%d",&a[i]);
        if (a[i] < l) l = a[i];
        if (a[i] > r) r = a[i];
    }
    sum = 1LL * n * (n - 1) / 2 + n;
    int ans = -1,mid;
    while (l<=r){
        mid = (l+r)>>1;
        if (check(mid)) {
            ans = mid, l = mid + 1;
        }else {
            r = mid - 1;
        }
    }
    printf("%d\n",ans);
}
int main(){
    while (~scanf("%d",&n)) work();
    return 0;
}



```