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;

const int N = 100005;
const int M = (1<<18);
ll p;
int n;
int t [N];
int tree [M+M];

void update (int u) {
	for (u+=N+M; u>=1; u/=2)
		tree[u]++;
	}

int query (int a, int b)
	{
	a += N+M;
	b += N+M;
	int res = tree[a] + tree[b];
	while (a/2 != b/2)
		{
		if (a%2==0) res += tree[a+1];
		if (b%2==1) res += tree[b-1];
		a /= 2;
		b /= 2;
		}
	return res;
	}

bool check (int m)
	{
	int i;
	for (i=0; i<M+M; i++)
		tree[i] = 0;
	update(0);
	ll out = 0;
	int pre = 0;
	for (i=1; i<=n; i++)
		{
		pre += ((t[i]<=m) ? -1 : 1);
		out += query(pre+1, n+1);
		update(pre);
		}
	if (p%2==0) return (2*out >= p+2);
	if (p%2==1) return (2*out >= p+1);
	}

int main ()
	{
	int i, a, b;
	scanf ("%d", &n);
	p = (1ll*(n+1)*n)/2;
	for (i=1; i<=n; i++)
		scanf ("%d", &t[i]);
	a = -1;
	b = 1000000001;
	while (b-a>1)
		(check((a+b)/2) ? b : a) = (a+b)/2;
	printf ("%d\n", b);
	return 0;
	}
