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

int main() {
	long long n;cin>>n;
	vector<int> a(n),s(n),l(n+1);
	l[0]=0;
	for(int i=0;i<n;i++){
		cin>>a[i];
		s[i]=a[i];
	}
	sort(s.begin(),s.end());
	int right=n-1;
	int left=0;
	while(right!=left){
		int j=(right+left+1)/2;
		int num=s[j];
//		cout<<i<<' '<<num<<endl;
		for(int i=0;i<n;i++){
			if(a[i]>=num){
				l[i+1]=1;
			}else{
				l[i+1]=-1;
			}
		}
		for(int i=1;i<=n;i++)l[i]+=l[i-1];
//		for(int i=0;i<=n;i++)cout<<l[i]<<' ';
//		cout<<endl;
		long long count;
		long long t=0;
		vector<long long> bit(2*n+2,0);
		for(int i=0;i<n+1;i++){
			int first=l[i]+n+1;
//			int k=0;
			for(int x=first;x<=2*n+1;x+=x&-x){
				bit[x]++;
//				cout<<x;
//				if(k<10){
//					k++;
//				}else{
//					break;
//				}
			}
			long long sum=0;
//			cout<<'A';
			for(int x=first;x>=1;x-=x&-x)sum+=bit[x];
			t+=i+1-sum;
		}
		count=n*(n+1)/2-t;
//		cout<<i<<' '<<count<<endl;
		if(count>=(n*(n+1)/2+1)/2){
			left=j;
		}else{
			right=j-1;
		}
	}
	cout<<s[left]<<endl;
	return 0;
}
### Prompt

Create a solution in cpp for 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<algorithm>
using namespace std;

int main() {
	long long n;cin>>n;
	vector<int> a(n),s(n),l(n+1);
	l[0]=0;
	for(int i=0;i<n;i++){
		cin>>a[i];
		s[i]=a[i];
	}
	sort(s.begin(),s.end());
	int right=n-1;
	int left=0;
	while(right!=left){
		int j=(right+left+1)/2;
		int num=s[j];
//		cout<<i<<' '<<num<<endl;
		for(int i=0;i<n;i++){
			if(a[i]>=num){
				l[i+1]=1;
			}else{
				l[i+1]=-1;
			}
		}
		for(int i=1;i<=n;i++)l[i]+=l[i-1];
//		for(int i=0;i<=n;i++)cout<<l[i]<<' ';
//		cout<<endl;
		long long count;
		long long t=0;
		vector<long long> bit(2*n+2,0);
		for(int i=0;i<n+1;i++){
			int first=l[i]+n+1;
//			int k=0;
			for(int x=first;x<=2*n+1;x+=x&-x){
				bit[x]++;
//				cout<<x;
//				if(k<10){
//					k++;
//				}else{
//					break;
//				}
			}
			long long sum=0;
//			cout<<'A';
			for(int x=first;x>=1;x-=x&-x)sum+=bit[x];
			t+=i+1-sum;
		}
		count=n*(n+1)/2-t;
//		cout<<i<<' '<<count<<endl;
		if(count>=(n*(n+1)/2+1)/2){
			left=j;
		}else{
			right=j-1;
		}
	}
	cout<<s[left]<<endl;
	return 0;
}
```