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;
typedef long long ll;
typedef pair<int,int> P;

#define int long long

int N;
int A[100005];
int low, high;

int bit[300005];
int dat[300005];

int sum(int i){
	int ret = 0;
	while(i > 0){
		ret += bit[i];
		i -= i & -i ;
	}
	return ret;
}

void add(int i, int x){
	while(i <= N*2+100){
		bit[i] += x;
		i += i & -i;
	}
	return;
}

bool is_bigger(int val){
	memset(bit,0,sizeof(bit));
	memset(dat,0,sizeof(dat));

	dat[0] = N+10;
	for (int i = 0;i < N;i++){
		if(A[i] < val) dat[i+1] = dat[i]-1;
		else dat[i+1] = dat[i]+1;
	}

	ll s = 0;
	for (int i = 0;i <= N;i++){
		s += sum(dat[i]);
		add(dat[i],1);
	}
	
	ll all = (N*(N+1))/2;

	//cout << val << " " << s << endl;

	if(s*2 >= all) return true;
	else return false;

}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	cin >> N;

	low  = INT_MAX;
	high = INT_MIN;

	for (int i = 0;i < N;i++){
		cin >> A[i];
		low = min(low, A[i]);
		high = max(high, A[i]);
	}

	high++;

	while(high-low > 1){
		int mid = (low+high)/2;
		if(is_bigger(mid)) low = mid;
		else high = mid;
	}

	cout << low << endl;

	return 0;

}
