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;
int n,a[100005],sum[100005],temp[100005];
long long cnt,num;
void merge_sort(int l,int r)
{
	if(l>=r) return;
	int mid=(l+r)/2;
	merge_sort(l,mid);
	merge_sort(mid+1,r);
	int i=l,j=mid+1,k=l;
	while(i<=mid&&j<=r)
	{
		if(sum[i]<=sum[j]) temp[k++]=sum[i++];
		else cnt+=mid-i+1,temp[k++]=sum[j++];
	}
	while(i<=mid) temp[k++]=sum[i++];
	while(j<=r) temp[k++]=sum[j++];
	for(i=l;i<=r;i++) sum[i]=temp[i];
}
bool check(int x)
{
	sum[0]=cnt=0;
	for(int i=1;i<=n;i++) sum[i]=a[i]<=x?-1:1;
	for(int i=1;i<=n;i++) sum[i]+=sum[i-1];
	merge_sort(0,n);
	return cnt>=num/2+1;
}
int main()
{
	int l=INT_MAX,r=INT_MIN;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),l=min(l,a[i]),r=max(r,a[i]),num+=i;
	while(l<r)
	{
		int mid=(l+r)/2;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	cout<<r<<endl;
	return 0;
}