#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int M = 100000;

int n;
int da[100010];
int f[100010];
long long p[200010];

inline int lowbit(int x){return x&(-x);}

void up(int pos, int val){
	for(int i = pos; i <= 2*n+1; i += lowbit(i)){
		p[i] += val;
	}
}

long long que(int pos){
	long long ans = 0;
	for(int i = pos; i; i -= lowbit(i)){
		ans += p[i];
	}
	return ans;
}

long long calc(int x){
	memset(f, 0, sizeof(f));
	memset(p, 0, sizeof(p));
	for(int i = 1; i <= n; i ++){
		if(da[i] >= x) f[i] = 1;
		else f[i] = -1; 
		f[i] += f[i-1];
	}
	long long res = 0;
	up(n+1, 1);
	for(int i = 1; i <= n; i ++){
		up(f[i]+n+1, 1);
		res += que(2*n+1) - que(f[i]+n+1);
	}
	return res;
}

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++){
		scanf("%d", &da[i]);
	}
	if(n == 1) {printf("%d\n", da[1]); return 0;}
	int l = 1, r = 1e9+1, ans = 0;
	while(l <= r){
		int mid = (l+r) >> 1;
		if(calc(mid) <= ((long long)(1+n)*n/2)/2 + 1){
			l = mid + 1, ans = mid;
		}else r = mid - 1;
	} 
	printf("%d\n", ans);
	return 0;	
}
### Prompt

Please formulate a cpp solution to 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 <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int M = 100000;

int n;
int da[100010];
int f[100010];
long long p[200010];

inline int lowbit(int x){return x&(-x);}

void up(int pos, int val){
	for(int i = pos; i <= 2*n+1; i += lowbit(i)){
		p[i] += val;
	}
}

long long que(int pos){
	long long ans = 0;
	for(int i = pos; i; i -= lowbit(i)){
		ans += p[i];
	}
	return ans;
}

long long calc(int x){
	memset(f, 0, sizeof(f));
	memset(p, 0, sizeof(p));
	for(int i = 1; i <= n; i ++){
		if(da[i] >= x) f[i] = 1;
		else f[i] = -1; 
		f[i] += f[i-1];
	}
	long long res = 0;
	up(n+1, 1);
	for(int i = 1; i <= n; i ++){
		up(f[i]+n+1, 1);
		res += que(2*n+1) - que(f[i]+n+1);
	}
	return res;
}

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++){
		scanf("%d", &da[i]);
	}
	if(n == 1) {printf("%d\n", da[1]); return 0;}
	int l = 1, r = 1e9+1, ans = 0;
	while(l <= r){
		int mid = (l+r) >> 1;
		if(calc(mid) <= ((long long)(1+n)*n/2)/2 + 1){
			l = mid + 1, ans = mid;
		}else r = mid - 1;
	} 
	printf("%d\n", ans);
	return 0;	
}
```