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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10;
ll f[N*4];
vector<ll> v;
void upd(ll pos, ll val)
{
	for(int i=pos; i<N*4; i += i&-i) f[i] += val;
}

ll query(ll pos)
{
	ll res = 0;
	for(int i=pos; i>0; i -= i&-i) res += f[i];
	return res;
} 

bool check(ll m, ll sz)
{
	memset(f, 0, sizeof(f));
	ll inv = 0;
	ll n = sz;
	vector<ll> tmp(n+1);
	tmp[0] = 0;
	for(int i=0; i<n; i++)
		tmp[i+1] = tmp[i]  + (v[i] >= m?1:-1);
	for(int i=0; i<=n; i++)
	{
		ll ind = tmp[i] + N + 1;
		inv += query(ind);
		upd(ind, 1);
	} 
	ll total = (n*(n+1)) /2;
	ll obj = (total+1) /2;
	if(inv>= obj) return true;
	else return false;
}

int main()
{
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(false);
    int n;
	cin>>n;
	v.resize(n);
	for(int i=0; i<n; i++) cin>>v[i];
	ll l = 0, r = 1 << 30;
	ll ans = 0;
	while(l <= r)
	{
		ll mid = l + (r-l) / 2;
		if(check(mid, n)) {ans = mid, l = mid + 1;}
		else r = mid - 1;
	}
	cout<<ans<<endl;
	return 0;
}
