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
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N = int(input())
aa = inpl()

def calc(x):
	aa_dush = [-1]*N
	for i in range(N):
		if aa[i] >= x:
			aa_dush[i] = 1
	#aa_dush = [1, 1, 1, 1, 1, 1, -1, 1, -1, -1]

	S = [0] #S_0 = 0を忘れずにつける
	tmp = 0
	MIN = MAX = 0
	for i in range(N):
		tmp += aa_dush[i]
		MIN = min(tmp,MIN)
		MAX = max(tmp,MAX)
		S.append(tmp)
	#S = [0, 1, 2, 3, 4, 5, 6, 5, 6, 5, 4]
	#MIN = 0 , MAX = 6

	L = (MAX-MIN+1) #BITのサイズ L=6
	bit = [0]*(L+1) #1indexで扱うのでL+1の長さで取る
	ans = 0
	for S_i in S:
		S_i -= (MIN-1) #S_iの最小値が1となるように調整

		#BITで既出の要素のうちS_i以下の要素数をカウント
		tmp = 0
		x = S_i
		while x > 0:
			tmp += bit[x]
			x -= x & -x
		ans += tmp

		#BITのS_iに1を加算して更新
		x = S_i
		while x <= L:
			bit[x] += 1
			x += x & -x

	return ans #中央値がx以上となる(l,r)の組の数

border = ( (N+1)*N//2 +1 )//2
OK = 0
NG = 10**9+3

while NG - OK > 1:
	mid = (OK+NG)//2
	if calc(mid) >= border:
		OK = mid
	else:
		NG = mid

print(OK)
