#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;


const int INF = 1e+9;

// num より大きい数がいくつあるかを求める
// 転倒数 (i<j かつ a[i]>a[j] となる組の数) の求め方とほぼ同じ
long long check( int num, vector<int>& a )
{
    int N = a.size();
    long long ret = 0, now = 0;
    unordered_map<int,int> count;  // count[i]: iが現れた回数
    vector<int> ps(N);

    count[0] = 1;
    for( int i = 0; i < N; ++i ){
        // a[i] > num となる数を求める
        ps[i] = (i? ps[i-1]: 0) + (a[i]<=num? 1: -1);
        if( a[i] <= num ) now += count[ps[i]-1];
        else now -= count[ps[i]];
        ++count[ps[i]];
        ret += now;
    }

    return ret;
}


int main()
{
    int N;
    cin >> N;
    vector<int> a(N);    
    for( int i = 0; i < N; ++i ) cin >> a[i];


    // 中央値になる値を二分探索
    // 数列 M には、中央値より大きい数がちょうど [M/2] あることを利用
    int l = 0, r = INF;
    long long want = 1LL*(N+1)*N/4 + 1;  //　自分より大きい数がこれだけあればOK
    while(r-l > 1){
        int c = (l+r)/2;
        if( check(c, a) >= want ) r = c;
        else l = c;
    }
    cout << r << endl;
    return 0;
}
### Prompt

In cpp, your task is to solve the following problem:

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 <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;


const int INF = 1e+9;

// num より大きい数がいくつあるかを求める
// 転倒数 (i<j かつ a[i]>a[j] となる組の数) の求め方とほぼ同じ
long long check( int num, vector<int>& a )
{
    int N = a.size();
    long long ret = 0, now = 0;
    unordered_map<int,int> count;  // count[i]: iが現れた回数
    vector<int> ps(N);

    count[0] = 1;
    for( int i = 0; i < N; ++i ){
        // a[i] > num となる数を求める
        ps[i] = (i? ps[i-1]: 0) + (a[i]<=num? 1: -1);
        if( a[i] <= num ) now += count[ps[i]-1];
        else now -= count[ps[i]];
        ++count[ps[i]];
        ret += now;
    }

    return ret;
}


int main()
{
    int N;
    cin >> N;
    vector<int> a(N);    
    for( int i = 0; i < N; ++i ) cin >> a[i];


    // 中央値になる値を二分探索
    // 数列 M には、中央値より大きい数がちょうど [M/2] あることを利用
    int l = 0, r = INF;
    long long want = 1LL*(N+1)*N/4 + 1;  //　自分より大きい数がこれだけあればOK
    while(r-l > 1){
        int c = (l+r)/2;
        if( check(c, a) >= want ) r = c;
        else l = c;
    }
    cout << r << endl;
    return 0;
}
```