AtCoder Beginner Contest 107 - Median of Medians

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.

-----Sample Input-----
3
10 30 20

-----Sample Output-----
30

The median of each contiguous subsequence of a is as follows:
 - The median of (10) is 10.
 - The median of (30) is 30.
 - The median of (20) is 20.
 - The median of (10, 30) is 30.
 - The median of (30, 20) is 30.
 - The median of (10, 30, 20) is 20.
Thus, m = (10, 30, 20, 30, 30, 20) and the median of m is 30.

Difficulty: MEDIUM_HARD

Starter code:

Solutions:
class Bit:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.tree[i] += x
			i += i & -i
n = int(input())
a = list(map(int, input().split()))

def med(x):
	cum = [0] * (n + 1)
	for i in range(n):
		if a[i] >= x:
			cum[i + 1] = cum[i] + 1
		else:
			cum[i + 1] = cum[i] - 1
	m = min(cum)
	for i in range(n + 1):
		cum[i] -= m - 1
	zb = Bit(max(cum))
	ret = 0
	for j in range(n + 1):
		ret += zb.sum(cum[j])
		zb.add(cum[j], 1)
	return ret
b = sorted(a)
l = 0
r = n
while r - l > 1:
	mid = (l + r + 1) // 2
	if 2 * med(b[mid]) >= n * (n + 1) // 2:
		l = mid
	else:
		r = mid
print(b[l])


from itertools import accumulate
from math import ceil
N = int(input())
A = list(map(int, input().split()))

class BinaryIndexedTree:

	def __init__(self, n):
		self.size = n
		self.bit = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.bit[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.bit[i] += x
			i += i & -i

	def reset(self):
		self.bit = [0] * (self.size + 1)
(ok, ng) = (0, 10 ** 9 + 1)
BIT = BinaryIndexedTree(N + 1)
while abs(ok - ng) > 1:
	X = (ok + ng) // 2
	B = [1 if a >= X else -1 for a in A]
	B = [0] + list(accumulate(B))
	B_sorted = {b: i for (i, b) in enumerate(sorted(B), start=1)}
	tmp = 0
	BIT.reset()
	for (j, b) in enumerate(B):
		tmp += BIT.sum(B_sorted[b])
		BIT.add(B_sorted[b], 1)
	if tmp >= ceil(N * (N + 1) / 2 / 2):
		ok = X
	else:
		ng = X
print(ok)


n = int(input())
A = list(map(int, input().split()))

def search(x):
	b = n
	r = 0
	y = 0
	D = [0] * (2 * n + 1)
	for i in range(n):
		D[b] += 1
		if A[i] < x:
			r += D[b]
			b += 1
		else:
			b -= 1
			r -= D[b]
		y += r
	return y
S = sorted(A)
l = 0
r = n
m = n // 2
c = n * (n + 1) // 2
while True:
	if search(S[m]) <= c // 2:
		if m == n - 1:
			break
		elif search(S[m + 1]) > c // 2:
			break
		else:
			l = m
			m = (m + r) // 2
	else:
		r = m + 1
		m = (m + l) // 2
print(S[m])


n = int(input())
a = list(map(int, input().split()))

class BIT:

	def __init__(self, n):
		self.size = n
		self.bit = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.bit[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.bit[i] += x
			i += i & -i
ok = 0
ng = 10 ** 9 + 1

def inversion(a, bit):
	ans = 0
	for (i, p) in enumerate(b):
		bit.add(p, 1)
		ans += i + 1 - bit.sum(p)
	return ans
while ng - ok > 1:
	m = ok + (ng - ok) // 2
	b = [0]
	for i in range(n):
		if a[i] >= m:
			b.append(b[i] + 1)
		else:
			b.append(b[i] - 1)
	b = [i + 100001 for i in b]
	bit = BIT(200005)
	inversion = 0
	for (i, p) in enumerate(b):
		bit.add(p, 1)
		inversion += i + 1 - bit.sum(p)
	if inversion <= n * (n + 1) // 4:
		ok = m
	else:
		ng = m
print(ok)


def main():
	(n, *a) = map(int, open(0).read().split())
	m = n * -~n // 2 + 1 >> 1
	ng = max(a) + 1
	ok = 0
	while ng - ok > 1:
		mid = ok + ng >> 1
		b = [1] + [0] * n * 2
		c = d = s = 0
		for t in a:
			if t >= mid:
				c += 1
				d += b[c] + 1
			else:
				d -= b[c] - 1
				c -= 1
			b[c] += 1
			s += d
		if s >= m:
			ok = mid
		else:
			ng = mid
	print(ok)
main()


from math import ceil
from itertools import accumulate
n = int(input())
import math
import decimal
import collections
import itertools
import sys

def find(x):
	if par[x] < 0:
		return x
	else:
		par[x] = find(par[x])
		return par[x]

def unite(x, y):
	p = find(x)
	q = find(y)
	if p == q:
		return None
	if p > q:
		(p, q) = (q, p)
	par[p] += par[q]
	par[q] = p

def same(x, y):
	return find(x) == find(y)

def size(x):
	return -par[find(x)]
par = [-1 for i in range(n)]

def prime_numbers(x):
	if x < 2:
		return []
	prime_numbers = [i for i in range(x)]
	prime_numbers[1] = 0
	for prime_number in prime_numbers:
		if prime_number > math.sqrt(x):
			break
		if prime_number == 0:
			continue
		for composite_number in range(2 * prime_number, x, prime_number):
			prime_numbers[composite_number] = 0
	return [prime_number for prime_number in prime_numbers if prime_number != 0]

def is_prime(x):
	if x < 2:
		return False
	if x == 2 or x == 3 or x == 5:
		return True
	if x % 2 == 0 or x % 3 == 0 or x % 5 == 0:
		return False
	prime_number = 7
	difference = 4
	while prime_number <= math.sqrt(x):
		if x % prime_number == 0:
			return False
		prime_number += difference
		difference = 6 - difference
	return True
mod = 10 ** 9 + 7

def comb(n, r):
	if n < r:
		return 0
	if n < 0 or r < 0:
		return 0
	return fa[n] * fi[r] % mod * fi[n - r] % mod
fa = [1] * (n + 1)
fi = [1] * (n + 1)
for i in range(1, n + 1):
	fa[i] = fa[i - 1] * i % mod
	fi[i] = pow(fa[i], mod - 2, mod)

def add(i, x):
	while i <= len(BIT):
		BIT[i] += x
		i += i & -i

def query(i):
	s = 0
	while i > 0:
		s += BIT[i]
		i -= i & -i
	return s
a = list(map(int, input().split()))
lis = sorted(list(set(a)))
(l, r) = (0, len(lis))
while r - l > 1:
	BIT = [0] * (2 * (n + 1) + 100)
	m = (l + r) // 2
	cum = [0]
	for i in range(n):
		cur = 1 if a[i] >= lis[m] else -1
		cum.append(cum[-1] + cur)
	cnt = 0
	for i in range(n + 1):
		cur = n + cum[i] + 5
		cnt += query(cur)
		add(cur, 1)
	if n * (n + 1) // 2 <= cnt * 2:
		l = m
	else:
		r = m
print(lis[l])


n = int(input())
a = list(map(int, input().split()))

class Bit:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		if not 0 <= i < self.size:
			raise ValueError('error!')
		i += 1
		while i <= self.size:
			self.tree[i] += x
			i += i & -i

def search(x):
	l = [1 if i >= x else -1 for i in a]
	c = [n]
	for i in range(n):
		c.append(c[-1] + l[i])
	count = 0
	bit = Bit(2 * n + 1)
	for i in c:
		count += bit.sum(i + 1)
		bit.add(i, 1)
	return (x, count)
k = (n * (n + 1) / 2 + 1) // 2
le = 0
ri = max(a) + 1
while ri > le + 1:
	m = (ri + le) // 2
	(ans, count) = search(m)
	if count >= k:
		le = m
	else:
		ri = m
print(le)


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce
sys.setrecursionlimit(2147483647)
INF = 10 ** 18

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def I():
	return int(sys.stdin.buffer.readline())

def LS():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

def S():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8')

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]

def SRL(n):
	return [list(S()) for i in range(n)]

def MSRL(n):
	return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

class BIT:

	def __init__(self, size):
		self.bit = [0] * size
		self.size = size

	def add(self, i, w):
		x = i + 1
		while x <= self.size:
			self.bit[x - 1] += w
			x += x & -x
		return

	def sum(self, i):
		res = 0
		x = i + 1
		while x:
			res += self.bit[x - 1]
			x -= x & -x
		return res
n = I()
A = LI()

def D(L):
	n = len(L)
	bit = BIT(2 * n + 1)
	ans = 0
	for i in range(n - 1, -1, -1):
		bit.add(L[i] + n, 1)
		ans += bit.sum(L[i] + n - 1)
	return ans
ALL = (n + 1) * n // 2
A2 = sorted(A)
(ng, ok) = (n, 0)
while ng > ok + 1:
	mid = (ok + ng) // 2
	L = [0] + list(accumulate([1 if i >= A2[mid] else -1 for i in A]))
	if D(L) >= ALL // 2 + 1:
		ng = mid
	else:
		ok = mid
print(A2[ok])


n = int(input())
a = list(map(int, input().split()))
x = list(sorted(set(a)))
n_sub = n * (n + 1) // 2
Li = 0
Ri = len(x)
while Ri > Li + 1:
	i = (Li + Ri) // 2
	xi = x[i]
	UorD = [1 if ak >= xi else -1 for ak in a]
	cnt_sum = [0] * (2 * n + 1)
	cumsum = 0
	cnt_sum[cumsum + n] = 1
	judge = 0
	s = 0
	for uk in UorD:
		cumsum += uk
		if uk == 1:
			s += cnt_sum[cumsum + n] + 1
		else:
			s -= cnt_sum[cumsum + n + 1] - 1
		cnt_sum[cumsum + n] += 1
		judge += s
		if judge >= n_sub // 2:
			Li = i
			break
	else:
		Ri = i
print(x[Li])


n = int(input())
a = list(map(int, input().split()))
m = n * (n + 1) // 2 // 2 + 1

class BIT1:

	def __init__(self, n):
		self.n = n
		self.bit = [0] * (self.n + 1)
		self.data = [0] * (self.n + 1)

	def add(self, idx, x):
		self.data[idx] += x
		while idx <= self.n:
			self.bit[idx] += x
			idx += idx & -idx

	def sum(self, idx):
		s = 0
		while idx:
			s += self.bit[idx]
			idx -= idx & -idx
		return s

def check(x):
	s = 0
	c = [0] * (n + 1)
	for i in range(n):
		c[i + 1] = c[i]
		if a[i] <= x:
			c[i + 1] += 1
	d = [2 * c[i] - i + n + 1 for i in range(n + 1)]
	d_max = max(d)
	bit = BIT1(d_max)
	cnt = 0
	for i in range(n + 1):
		cnt += bit.sum(d[i] - 1)
		bit.add(d[i], 1)
	return cnt >= m
lb = 0
ub = max(a) + 1
while ub - lb > 1:
	mid = (ub + lb) // 2
	if check(mid):
		ub = mid
	else:
		lb = mid
print(ub)


import math

class Bit:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.tree[i] += x
			i += i & -i

	def reset(self):
		t = self.tree
		for i in range(len(t)):
			t[i] = 0
get_ints = lambda : [int(st) for st in input().split()]
N = int(input())
inarr = get_ints()
sorted_in = sorted(inarr)
comb = N * (N + 1) // 2
bit = Bit(2 * N + 1)

def binsearch(lft, rgt):
	half = (lft + rgt) // 2
	if lft >= half:
		return half
	summed = 0
	res = 0
	bit.reset()
	bit.add(N, 1)
	for x in inarr:
		value = 1 if x >= sorted_in[half] else -1
		summed += value
		count = bit.sum(N + summed)
		bit.add(N + summed, 1)
		res += count
	return binsearch(half, rgt) if res >= math.ceil(comb / 2) else binsearch(lft, half)
res = binsearch(0, N)
print(sorted_in[res])


from itertools import accumulate
from collections import defaultdict

class Bit:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.tree[i] += x
			i += i & -i
n = int(input())
a = list(map(int, input().split()))

def jdg(x):
	b = [0 for i in range(n)]
	for i in range(n):
		if a[i] >= x:
			b[i] = 1
		else:
			b[i] = -1
	acc = [0] + list(accumulate(b))
	mn = min(acc)
	mx = max(acc)
	dif = mx - mn
	bit = Bit(dif + 2)
	ret = 0
	for i in range(n + 1):
		p = acc[i] - mn + 1
		ret += bit.sum(p)
		bit.add(p, 1)
	return ret
l = 0
r = max(a) + 1
while l + 1 < r:
	x = (l + r) // 2
	if jdg(x) >= (n + 1) * n // 4:
		l = x
	else:
		r = x
print(l)


N = int(input())
src = list(map(int, input().split()))
cands = list(sorted(set(src)))

def enough(i):
	bit = [0] * (2 * N + 10)

	def bit_add(a, w):
		x = a
		while x <= 2 * N + 9:
			bit[x] += w
			x += x & -x

	def bit_sum(a):
		x = a
		ret = 0
		while x > 0:
			ret += bit[x]
			x -= x & -x
		return ret
	cums = [0]
	for a in src:
		tmp = 1 if a >= cands[i] else -1
		cums.append(cums[-1] + tmp)
	cnt = 0
	for i in range(N + 1):
		a = cums[i] + N + 5
		cnt += bit_sum(a)
		bit_add(a, 1)
	return cnt * 2 >= N * (N + 1) // 2
ok = 0
ng = len(cands)
while ng - ok > 1:
	m = (ok + ng) // 2
	if enough(m):
		ok = m
	else:
		ng = m
print(cands[ok])


from itertools import accumulate

class BIT_RSQ:

	def __init__(self, n):
		self.n = n
		self.data = [0] * (n + 1)

	def add(self, i, v):
		while i <= self.n:
			self.data[i - 1] += v
			i += i & -i

	def sum(self, i):
		ret = 0
		while i > 0:
			ret += self.data[i - 1]
			i -= i & -i
		return ret
n = int(input())
a = list(map(int, input().split()))

def check(m):
	b = [[-1, 1][i >= m] for i in a]
	bit = BIT_RSQ(2 * n + 1)
	s = [0] + list(accumulate(b))
	res = 0
	for i in range(n):
		bit.add(s[i] + n + 1, 1)
		res += bit.sum(s[i + 1] + n + 1)
	return res >= (n * (n + 1) // 2 + 1) // 2
left = 0
right = 10 ** 9 + 1
while right - left > 1:
	mid = (right + left) // 2
	if check(mid):
		left = mid
	else:
		right = mid
print(left)


import os
import sys
if os.getenv('LOCAL'):
	sys.stdin = open('_in.txt', 'r')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
IINF = 10 ** 18
MOD = 10 ** 9 + 7

class BinaryIndexedTree:

	def __init__(self, size):
		self._bit = [0] * size
		self._size = size

	def add(self, i, w):
		x = i + 1
		while x <= self._size:
			self._bit[x - 1] += w
			x += x & -x

	def sum(self, i):
		ret = 0
		while i > 0:
			ret += self._bit[i - 1]
			i -= i & -i
		return ret

	def __len__(self):
		return self._size

def median(A):
	return list(sorted(A))[len(A) // 2]

def test(A):
	N = len(A)
	M = []
	for l in range(N):
		for r in range(l + 1, N + 1):
			M.append(median(A[l:r]))
	print(median(M))

def less_than(k):
	arr = [0] * (N + 1)
	for (i, b) in enumerate(B):
		arr[i + 1] = 1 if b >= k else -1
	cum = cumsum(arr)
	base = min(cum)
	for i in range(len(cum)):
		cum[i] -= base
	bit = BinaryIndexedTree(size=max(cum) + 1)
	count = 0
	for (i, c) in enumerate(cum):
		count += i - bit.sum(c + 1)
		bit.add(c, 1)
		if count > (N + 1) * N // 2 / 2:
			return True
	return False

def compress(li, origin=0):
	(*ret,) = map({v: i + origin for (i, v) in enumerate(sorted(set(li)))}.__getitem__, li)
	return ret

def argsort(li, key=None, reverse=False):
	return [i for (_, i) in sorted([(a, i) for (i, a) in enumerate(li)], key=(lambda t: key(t[0])) if key else None, reverse=reverse)]

def cumsum(it):
	cs = 0
	ret = []
	for v in it:
		cs += v
		ret.append(cs)
	return ret
N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))
indices = argsort(A)
B = compress(A)
lo = 0
hi = N
while abs(lo - hi) > 1:
	mid = (lo + hi) // 2
	if less_than(B[indices[mid]]):
		hi = mid
	else:
		lo = mid
print(A[indices[lo]])


class Bit:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.tree[i] += x
			i += i & -i
n = int(input())
A = list(map(int, input().split()))
all_pattern = n * (n + 1) // 2
check = all_pattern // 2 + bool(all_pattern % 2)
X = sorted(A)
left = 0
right = n
while left + 1 < right:
	idx = (left + right) // 2
	x = X[idx]
	up_or_down = [1 if num >= x else -1 for num in A]
	cumsum = [n]
	total = n
	for point in up_or_down:
		total += point
		cumsum.append(total)
	tree = Bit(2 * n + 1)
	pattern = 0
	for p in cumsum:
		pattern += tree.sum(p)
		tree.add(p, 1)
	if pattern >= check:
		left = idx
	else:
		right = idx
print(X[left])


N = int(input())
a_list = list(map(int, input().split()))

def search(c):
	bar = N
	r = 0
	res_nega = 0
	dp_arr = [0] * (2 * N + 1)
	for i in range(N):
		dp_arr[bar] += 1
		if a_list[i] < c:
			r += dp_arr[bar]
			bar += 1
		else:
			r -= dp_arr[bar - 1]
			bar -= 1
		res_nega += r
	return res_nega
a_sorted = sorted(a_list)
left = 0
right = N
mid = N // 2
C = N * (N + 1) // 2
while True:
	if search(a_sorted[mid]) <= C // 2:
		if mid == N - 1:
			break
		elif search(a_sorted[mid + 1]) > C // 2:
			break
		else:
			left = mid
			mid = (mid + right) // 2
	else:
		right = mid + 1
		mid = (mid + left) // 2
print(a_sorted[mid])


import sys
input = sys.stdin.readline
from itertools import accumulate
n = int(input())
m = (n * (n + 1) // 2 + 1) // 2
U = 2 ** 20
A = tuple(map(int, input().split()))

def test(x):
	L = [0] + list(accumulate(((-1) ** (a < x) for a in A)))
	B = [0] * (U + 1)

	def add(i):
		while i <= U:
			B[i] += 1
			i += i & -i

	def acc(i):
		res = 0
		while i:
			res += B[i]
			i -= i & -i
		return res
	cnt = 0
	for l in L:
		cnt += acc(l + n + 5)
		add(l + n + 5)
	return cnt >= m
ok = 0
ng = 10 ** 9 + 1
while ng - ok > 1:
	mid = (ng + ok) // 2
	if test(mid):
		ok = mid
	else:
		ng = mid
print(ok)


N = int(input())
A = [int(_) for _ in input().split()]

def sub_problem(x):
	S = [0] * (N + 1)
	for i in range(N):
		S[i + 1] = S[i] + 1 if A[i] >= x else S[i] - 1
	geta = abs(min(S)) + 1
	for i in range(N + 1):
		S[i] += geta
	forward = 0
	size = max(S)
	bit = [0] * (size + 1)
	for s in S:
		i = s
		while i > 0:
			forward += bit[i]
			i -= i & -i
		i = s
		while i <= size:
			bit[i] += 1
			i += i & -i
	return forward >= (M + 1) // 2
M = N * (N + 1) // 2
sorted_A = sorted(A)
inf = 0
sup = N
while sup - inf > 1:
	mid = (sup + inf) // 2
	x = sorted_A[mid]
	if sub_problem(x):
		inf = mid
	else:
		sup = mid
print(sorted_A[inf])


NN = 18
N = int(input())
A = [int(a) for a in input().split()]

def chk(k):
	s = 0
	c = 0
	BIT = [0] * (2 ** NN + 1)

	def add(i, x=1):
		i += 1 << NN - 1
		while i <= 2 ** NN:
			BIT[i] += x
			i += i & -i

	def getsum(i):
		ret = 0
		i += 1 << NN - 1
		while i != 0:
			ret += BIT[i]
			i -= i & -i
		return ret
	add(0)
	for i in range(N):
		if A[i] >= k:
			s += 1
		else:
			s -= 1
		c += getsum(s)
		add(s)
	if 4 * c >= N * (N + 1):
		return 1
	return 0
(l, r) = (0, 1 << 30)
while r - l > 1:
	m = (l + r) // 2
	if chk(m):
		l = m
	else:
		r = m
print(l)


n = int(input())
a = list(map(int, input().split()))
a2 = sorted(set(a))
L = len(a2)
if n == 1:
	print(a[0])
	return
elif n == 2:
	print(a[1])
	return
ng = L
ok = 0
while ng - ok > 1:
	check = a2[(ok + ng) // 2]
	cnt = 0
	idx = n
	cl = [0] * (2 * n + 1)
	cl[n] = 1
	Ru = 0
	for i in range(n):
		if a[i] < check:
			Ru -= cl[idx] - 1
			idx -= 1
		else:
			idx += 1
			Ru += cl[idx] + 1
		cnt += Ru
		cl[idx] += 1
	if cnt >= (n + 1) * n // 2 // 2:
		ok = (ok + ng) // 2
	else:
		ng = (ok + ng) // 2
print(a2[ok])


N = int(input())
A = list(map(int, input().split()))
NN = ((N + 1) * N // 2 + 1) // 2

def ok(x):
	B = [0] * (2 * N + 1)
	(res, cum, cur) = (0, 0, 0)
	B[0] += 1
	for a in A:
		if a >= x:
			cum += 1
			cur += B[cum] + 1
		else:
			cur -= B[cum] - 1
			cum -= 1
		B[cum] += 1
		res += cur
	return res >= NN
B = sorted(set(A))
l = 0
r = len(B)
while r - l > 1:
	m = (l + r) // 2
	if ok(B[m]):
		l = m
	else:
		r = m
print(B[l])


N = int(input())
a = [int(i) for i in input().split()]
half = (N * (N + 1) // 2 + 1) // 2

class BinaryIndexedTree:

	def __init__(self, N):
		self.N = N
		self.tree = [0] * (N + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.N:
			self.tree[i] += x
			i += i & -i

def check(x):
	b = [0] + [1 if a[i] >= x else -1 for i in range(N)]
	for i in range(1, N + 1):
		b[i] += b[i - 1]
	BIT = BinaryIndexedTree(2 * N + 2)
	ret = 0
	for i in range(N + 1):
		ret += BIT.sum(N + 1 + b[i])
		BIT.add(N + 1 + b[i], 1)
	return ret >= half
aa = sorted(a)
ok = 0
ng = N
while ng - ok > 1:
	mid = (ok + ng) // 2
	if check(aa[mid]):
		ok = mid
	else:
		ng = mid
print(aa[ok])


import sys
readline = sys.stdin.readline

class BIT:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)
		self.p = 2 ** (n.bit_length() - 1)
		self.dep = n.bit_length()

	def get(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.tree[i] += x
			i += i & -i

	def bl(self, v):
		if v <= 0:
			return -1
		s = 0
		k = self.p
		for _ in range(self.dep):
			if s + k <= self.size and self.tree[s + k] < v:
				s += k
				v -= self.tree[s + k]
			k //= 2
		return s + 1

def compress(L):
	L2 = list(set(L))
	L2.sort()
	C = {v: k for (k, v) in enumerate(L2)}
	return (L2, C)
N = int(readline())
A = list(map(int, readline().split()))
(A2, C) = compress(A)
A = [C[a] for a in A]
ok = 0
ng = max(A) + 1
T = BIT(ng)
ma = min(A) + 1
while abs(ok - ng) > 1:
	med = (ok + ng) // 2
	B = [1 if a >= med else -1 for a in A]
	for i in range(1, N):
		B[i] += B[i - 1]
	mb = -min(0, min(B)) + 1
	T = BIT(max(B) + mb)
	T.add(mb, 1)
	res = 0
	for b in B:
		res += T.get(mb + b)
		T.add(mb + b, 1)
	if res >= N * (N + 1) // 4:
		ok = med
	else:
		ng = med
print(A2[ok])


from itertools import accumulate
from math import *
import os, sys
from io import BytesIO
input = BytesIO(os.read(0, os.fstat(0).st_size)).readline
N = int(input())
A = list(map(int, input().split()))

class FenV:

	def __init__(self, n):
		self.size = n
		self.bit = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.bit[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.bit[i] += x
			i += i & -i

	def reset(self):
		self.bit = [0] * (self.size + 1)
BIT = FenV(N + 1)
(ng, ok) = (10 ** 9 + 1, 0)
while abs(ok - ng) > 1:
	X = (ok + ng) // 2
	B = [1 if a >= X else -1 for a in A]
	B = [0] + list(accumulate(B))
	tmp = 0
	B_sorted = {b: i for (i, b) in enumerate(sorted(B), start=1)}
	BIT.reset()
	for (j, b) in enumerate(B):
		tmp += BIT.sum(B_sorted[b])
		BIT.add(B_sorted[b], 1)
	if tmp >= ceil(N * (N + 1) // 2 / 2):
		ok = X
	else:
		ng = X
print(ok)


import sys
from itertools import accumulate

def I():
	return int(sys.stdin.readline().rstrip())

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))

class BIT:

	def __init__(self, init_value):
		self.n = len(init_value)
		self.tree = [0] * (self.n + 1)
		for i in range(1, self.n + 1):
			x = init_value[i - 1]
			while i <= self.n:
				self.tree[i] += x
				i += i & -i

	def update(self, i, x):
		while i <= self.n:
			self.tree[i] += x
			i += i & -i
		return

	def query(self, i):
		res = 0
		while i > 0:
			res += self.tree[i]
			i -= i & -i
		return res
N = I()
A = LI()

def f(x):
	B = [0] + [1 if A[i] >= x else -1 for i in range(N)]
	B = list(accumulate(B))
	B = [b + N for b in B]
	bit = BIT([0] * (2 * N + 2))
	count = 0
	for i in range(N + 1):
		b = B[i]
		count += bit.query(b + 1)
		bit.update(b + 1, 1)
	return True if count >= (N * (N + 1) + 3) // 4 else False
ok = 1
ng = 10 ** 9 + 1
while ok + 1 < ng:
	mid = (ok + ng) // 2
	if f(mid):
		ok = mid
	else:
		ng = mid
print(ok)


def examA():
	(N, i) = LI()
	ans = N - i + 1
	print(ans)
	return

def examB():
	(H, W) = LI()
	A = [SI() for _ in range(H)]
	h = [[] for _ in range(H)]
	for i in range(W):
		flag = False
		for j in range(H):
			if A[j][i] == '#':
				flag = True
				break
		if flag:
			for j in range(H):
				h[j].append(A[j][i])
	ans = []
	for (i, a) in enumerate(h):
		if '#' in a:
			ans.append(i)
	for v in ans:
		print(''.join(map(str, h[v])))
	return

def examC():
	(N, K) = LI()
	X = LI()
	ans = inf
	for i in range(N - K + 1):
		if X[i] < 0 and X[i + K - 1] > 0:
			cur = -X[i] + X[i + K - 1] + min(-X[i], X[i + K - 1])
		else:
			cur = max(-X[i], X[i + K - 1])
		ans = min(ans, cur)
	print(ans)
	return

def examD():

	class Bit:

		def __init__(self, n):
			self.size = n
			self.tree = [0] * (n + 1)
			return

		def sum(self, i):
			s = 0
			while i > 0:
				s += self.tree[i]
				i -= i & -i
			return s

		def add(self, i, x):
			while i <= self.size:
				self.tree[i] += x
				i += i & -i
			return

	def inversion_number(n, A):
		bit = Bit(n + 1)
		rep = 0
		for (i, a) in enumerate(A):
			bit.add(a, 1)
			rep += i + 1 - bit.sum(a)
		return rep
	N = I()
	A = LI()
	judge = (N * (N + 1) // 2 + 1) // 2
	l = 0
	r = max(A) + 1
	while r - l > 1:
		now = (l + r) // 2
		S = [0] * (N + 1)
		cur = N * (N + 1) // 2
		for i in range(N):
			if A[i] >= now:
				S[i + 1] += 1
			else:
				S[i + 1] -= 1
		for i in range(1, N):
			S[i + 1] += S[i]
			S[i] += N + 1
		S[0] += N + 1
		S[N] += N + 1
		cur -= inversion_number(2 * N + 10, S)
		if cur >= judge:
			l = now
		else:
			r = now
	ans = l
	print(ans)
	return
import sys, copy, bisect, itertools, heapq, math, random
from heapq import heappop, heappush, heapify
from collections import Counter, defaultdict, deque

def I():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LSI():
	return list(map(str, sys.stdin.readline().split()))

def LS():
	return sys.stdin.readline().split()

def SI():
	return sys.stdin.readline().strip()
global mod, mod2, inf, alphabet, _ep
mod = 10 ** 9 + 7
mod2 = 998244353
inf = 10 ** 18
_ep = 10 ** (-12)
alphabet = [chr(ord('a') + i) for i in range(26)]
examD()


class BIT:

	def __init__(self, n):
		self.N = n
		self.n = 1 << n.bit_length()
		self.data = [0] * (self.n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.data[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.n:
			self.data[i] += x
			i += i & -i
N = int(input())
A = list(map(int, input().split()))
N0 = N * (N + 1) // 2

def C(x):
	B = BIT(N * 2 + 1)
	s = [0] * (N + 1)
	for i in range(N):
		a = A[i]
		s[i] = 1 if x < a else -1
		s[i] += s[i - 1]
	res = 0
	for i in range(-1, N):
		res += B.sum(s[i] + N + 1)
		B.add(s[i] + N + 1, 1)
	return res < N0 // 2
ok = max(A)
ng = min(A) - 1
while abs(ok - ng) > 1:
	mid = (ok + ng) // 2
	if C(mid):
		ok = mid
	else:
		ng = mid
print(ok)


class BIT:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * -~n

	def sum(self, i):
		s = 0
		while i:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.tree[i] += x
			i += i & -i
(n, *a) = map(int, open(0).read().split())
m = n * -~n // 2 + 1 >> 1
ng = max(a) + 1
ok = 0
while ng - ok > 1:
	mid = (ok + ng) // 2
	b = BIT(n - ~n)
	c = n + 1
	s = 0
	b.add(c, 1)
	for t in a:
		c += 1 if t >= mid else -1
		s += b.sum(c)
		b.add(c, 1)
	if s >= m:
		ok = mid
	else:
		ng = mid
print(ok)


N = int(input())
A = [int(_) for _ in input().split()]

class BIT:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.tree[i] += x
			i += i & -i

def sub_problem(x):
	S = [0] * (N + 1)
	for i in range(N):
		S[i + 1] = S[i] + 1 if A[i] >= x else S[i] - 1
	geta = abs(min(S)) + 1
	for i in range(N + 1):
		S[i] += geta
	forward = 0
	bit = BIT(max(S))
	for s in S:
		forward += bit.sum(s)
		bit.add(s, 1)
	return forward >= M // 2
M = N * (N + 1) // 2
sorted_A = sorted(A)
inf = 0
sup = N
while sup - inf > 1:
	mid = (sup + inf) // 2
	x = sorted_A[mid]
	if sub_problem(x):
		inf = mid
	else:
		sup = mid
print(sorted_A[inf])


import sys

def bit_add(iii, x):
	while iii < len(bit):
		bit[iii] += x
		iii += iii & -iii

def bit_sum(jjj):
	s = 0
	while jjj > 0:
		s += bit[jjj]
		jjj -= jjj & -jjj
	return s
n = int(input())
a = list(map(int, input().split()))
num = n * (n + 1) // 2
high = max(a)
low = min(a)
while high - low > 1:
	mid = (high + low) // 2
	ans = 0
	b = []
	for i in range(n):
		if a[i] >= mid:
			b.append(1)
		else:
			b.append(-1)
	for i in range(1, n):
		b[i] += b[i - 1]
	for i in range(n):
		b[i] += n
	bit = [0] * (2 * n + 3)
	bit_add(n, 1)
	for i in range(n):
		ans += bit_sum(b[i])
		bit_add(b[i], 1)
	if num % 2 == 1:
		if ans >= num // 2 + 1:
			low = mid
		else:
			high = mid
	elif ans >= num // 2:
		low = mid
	else:
		high = mid
if not high in a:
	print(low)
	sys.exit()
else:
	mid = high
	ans = 0
	b = []
	for i in range(n):
		if a[i] >= mid:
			b.append(1)
		else:
			b.append(-1)
	for i in range(1, n):
		b[i] += b[i - 1]
	for i in range(n):
		b[i] += n
	bit = [0] * (2 * n + 3)
	bit_add(n, 1)
	for i in range(n):
		ans += bit_sum(b[i])
		bit_add(b[i], 1)
	if num % 2 == 1:
		if ans >= num // 2 + 1:
			print(high)
		else:
			print(low)
	elif ans >= num // 2:
		print(high)
	else:
		print(low)


def add(B, a, n):
	x = a
	while x <= n:
		B[x] += 1
		x += x & -x

def sums(B, a):
	x = a
	S = 0
	while x != 0:
		S += B[x]
		x -= x & -x
	return S

def invnumber(n, S):
	B = [0] * (n * 2 + 1)
	invs = 0
	for i in range(n):
		s = S[i] + n
		invs += sums(B, s)
		add(B, s, n * 2)
	return invs
N = int(input())
A = list(map(int, input().split()))
R = max(A) + 1
L = 0
c = (N * (N + 1) // 2 + 1) // 2
while R - L > 1:
	M = (R + L) // 2
	S = [0] * (N + 1)
	for i in range(1, N + 1):
		if A[i - 1] >= M:
			S[i] = S[i - 1] + 1
		else:
			S[i] = S[i - 1] - 1
	if invnumber(N + 1, S) >= c:
		L = M
	else:
		R = M
print(L)


N = int(input())
A = [int(i) for i in input().split()]
AS = sorted(list(set(A)))

def f(x):
	B = [((x <= a) << 1) - 1 for a in A]
	C = [N]
	[C.append(C[-1] + b) for b in B]
	r = 0
	Bit = [0] * (2 * N + 1)
	for (i, c) in enumerate(C):
		t = c - 1
		while t > 0:
			r += Bit[t]
			t -= t & -t
		t = c - 1
		while t <= 2 * N + 1:
			Bit[t] += 1
			t += t & -t
	return r >= N * (N + 1) // 4
l = 0
r = len(AS) - 1
while l != r:
	if f(AS[(l + r + 1) // 2]):
		l = (l + r + 1) // 2
	else:
		r = (l + r + 1) // 2 - 1
print(AS[r])


N = int(input())
a = list(map(int, input().split()))
assert len(a) == N

def mergesort(S, f, t):
	global T
	if t - f <= 1:
		return 0
	mid = (f + t) // 2
	n1 = mergesort(S, f, mid)
	n2 = mergesort(S, mid, t)
	n = n1 + n2
	i = f
	j = mid
	k = f
	while i < mid and j < t:
		if S[i] <= S[j]:
			T[k] = S[i]
			i += 1
			n += t - j
		else:
			T[k] = S[j]
			j += 1
		k += 1
	while i < mid:
		T[k] = S[i]
		i += 1
		k += 1
	assert k == j
	for i in range(f, k):
		S[i] = T[i]
	return n

def inversion(S):
	global T
	T = [0] * len(S)
	return mergesort(S, 0, len(S))

def n_median_larger_than_or_equal_to(x):
	b = [-1 if e < x else 1 for e in a]
	S = [0]
	for e in b:
		S.append(S[-1] + e)
	return inversion(S)
lo = 1
hi = max(a)
ncomb = N * (N + 1) // 2
while lo < hi:
	mid = (lo + hi + 1) // 2
	nm = n_median_larger_than_or_equal_to(mid)
	if nm >= (ncomb + 1) // 2:
		lo = mid
	else:
		hi = mid - 1
print(lo)


def main():
	(N, *A) = map(int, open(0).read().split())
	B = sorted(A)
	(l, r) = (0, N)
	(m, c) = (N // 2, N * (N + 1) // 2)

	def check(x):
		(b, r, y) = (N, 0, 0)
		D = [0] * (2 * N + 1)
		for a in A:
			D[b] += 1
			if a < x:
				r += D[b]
				b += 1
			else:
				b -= 1
				r -= D[b]
			y += r
		return y
	while True:
		if check(B[m]) <= c // 2:
			if m == N - 1 or check(B[m + 1]) > c // 2:
				break
			else:
				(l, m) = (m, (m + r) // 2)
		else:
			(m, r) = ((m + l) // 2, m + 1)
	print(B[m])

def __starting_point():
	main()
__starting_point()


import numpy as np
from collections import defaultdict
N = int(input())
A = np.array(input().split(), dtype=np.int32)
total_medians = N * (N + 1) // 2

def test(x):
	current = 0
	memo = defaultdict(int)
	memo[0] = 1
	cnt_below = 1
	result = 0
	for a in A:
		if a > x:
			current += 1
			cnt_below += memo[current]
		else:
			cnt_below -= memo[current]
			current -= 1
		result += cnt_below
		memo[current] += 1
		cnt_below += 1
	return result <= (total_medians - 1) // 2
AA = sorted(A)
left = -1
right = len(AA) - 1
while right - left > 1:
	mid = (left + right) // 2
	if test(AA[mid]):
		right = mid
	else:
		left = mid
answer = AA[right]
print(answer)


from itertools import accumulate
from math import ceil

class BIT:

	def __init__(self, n):
		self.size = n
		self.bit = [0] * (n + 1)

	def add(self, i, x):
		while i <= self.size:
			self.bit[i] += x
			i += i & -i

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.bit[i]
			i -= i & -i
		return s

	def reset(self):
		self.bit = [0] * (self.size + 1)
n = int(input())
A = list(map(int, input().split()))
bit = BIT(n + 1)
(l, r) = (0, 10 ** 9 + 1)
while r - l > 1:
	mid = (l + r) // 2
	B = [1 if a >= mid else -1 for a in A]
	B = [0] + list(accumulate(B))
	cnt = 0
	B_sorted = {b: i for (i, b) in enumerate(sorted(B), start=1)}
	bit.reset()
	for b in B:
		cnt += bit.sum(B_sorted[b])
		bit.add(B_sorted[b], 1)
	if cnt >= ceil(n * (n + 1) // 2 / 2):
		l = mid
	else:
		r = mid
print(l)


import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
	from math import gcd
except Exception:
	from fractions import gcd

class BinaryIndexTree:

	def __init__(self, n):
		self._size = n
		self._tree = [0] * (n + 1)

	def sum(self, i):
		s = 0
		i += 1
		while 0 < i:
			s += self._tree[i - 1]
			i -= i & -i
		return s

	def add(self, i, x):
		i += 1
		while i <= self._size:
			self._tree[i - 1] += x
			i += i & -i

def solve(N: int, a: 'List[int]'):
	c = N * (N + 1) // 2
	th = (c + 1) // 2
	xs = list(sorted(set(a)))
	lo = 0
	hi = len(xs)

	def _f(x):
		ss = [0] + list(accumulate([1 if x <= v else -1 for v in a]))
		n = max([abs(s) for s in ss])
		bit = BinaryIndexTree(2 * n + 1)
		ret = 0
		for s in ss:
			ret += bit.sum(s + n)
			bit.add(s + n, 1)
		return ret
	while lo + 1 < hi:
		mid = (lo + hi) // 2
		if th <= _f(xs[mid]):
			lo = mid
		else:
			hi = mid
	return xs[lo]

def main():

	def iterate_tokens():
		for line in sys.stdin:
			for word in line.split():
				yield word
	tokens = iterate_tokens()
	N = int(next(tokens))
	a = [int(next(tokens)) for _ in range(N)]
	result = solve(N, a)
	print(result)
main()


n = int(input())
a = list(map(int, input().split()))
ary = a.copy()
ary = sorted(list(set(ary)))
from bisect import bisect_left
aa = [bisect_left(ary, x) for x in a]

class Bit:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)
		self.depth = n.bit_length()

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.tree[i] += x
			i += i & -i

def chk(x):
	c = [1 if ai <= x else -1 for ai in aa]
	cc = [0]
	tmp = 0
	(mi, ma) = (0, 0)
	for xx in c:
		tmp += xx
		cc.append(tmp)
		mi = min(mi, tmp)
		ma = max(ma, tmp)
	bit = Bit(ma - mi + 1)
	ret = 0
	for xx in cc:
		xx -= mi
		xx += 1
		bit.add(xx, 1)
		ret += bit.sum(xx - 1)
	return ret > (n + 1) * n // 2 // 2
(l, r) = (0, n)
while r - l > 1:
	x = (l + r) // 2
	if chk(x):
		(l, r) = (l, x)
	else:
		(l, r) = (x, r)
print(ary[l] if chk(l) else ary[r])


def cumsum(li):
	ret = []
	sum = 0
	for i in li:
		sum += i
		ret.append(sum)
	return ret

class BinaryIndexedTree:

	def __init__(self, size):
		self._bit = [0 for _ in range(size)]
		self._size = size

	def add(self, i, w):
		x = i + 1
		while x <= self._size:
			self._bit[x - 1] += w
			x += x & -x

	def sum(self, i):
		ret = 0
		x = i + 1
		while x > 0:
			ret += self._bit[x - 1]
			x -= x & -x
		return ret

	def __len__(self):
		return self._size

def count_inversions(li, max=None):
	if not max:
		max = __builtins__.max(li)
	bit = BinaryIndexedTree(size=max + 1)
	ret = 0
	for i in range(len(li)):
		ret += i - bit.sum(li[i])
		bit.add(li[i], 1)
	return ret

def bisect_left_callable(fn, x, lo, hi):
	while lo < hi:
		mid = (lo + hi) // 2
		if fn(mid) < x:
			lo = mid + 1
		else:
			hi = mid
	return lo
N = int(input())
series = list(map(int, input().split()))
series_sorted = sorted(series)
lr_size = (N + 1) * N / 2

def solve(i):
	x = series_sorted[i]
	cumsum_li = [0] + cumsum([1 if s >= x else -1 for s in series])
	inversions = count_inversions([N + i for i in cumsum_li], max=N + N)
	if lr_size - inversions >= (lr_size + 1) // 2:
		return i
	else:
		return float('inf')
ans_i = bisect_left_callable(solve, float('inf'), lo=0, hi=N)
print(series_sorted[max(0, min(N - 1, ans_i - 1))])


import sys

def input():
	return sys.stdin.readline().strip()

class BIT:

	def __init__(self, n):
		self.n = n
		self.data = [0] * (n + 1)
		self.el = [0] * (n + 1)

	def add(self, i, x):
		if i <= 0 or self.n < i:
			print('i should be within 1 to n')
		else:
			self.el[i] += x
			while i <= self.n:
				self.data[i] += x
				i += i & -i

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.data[i]
			i -= i & -i
		return s

	def get(self, i, j=None):
		if j is None:
			return self.el[i]
		return self.sum(j) - self.sum(i - 1)

def main():
	N = int(input())
	A = list(map(int, input().split()))
	left = 0
	right = 10 ** 9
	while right - left > 1:
		mid = (left + right) // 2
		B = [0] * (N + 1)
		for i in range(1, N + 1):
			if A[i - 1] <= mid:
				B[i] = B[i - 1] - 1
			if A[i - 1] > mid:
				B[i] = B[i - 1] + 1
		tree = BIT(2 * N + 1)
		cnt = 0
		for i in range(N + 1):
			tree.add(B[i] + N + 1, 1)
			cnt += tree.get(B[i] + N + 2, 2 * N + 1)
		if cnt > N * (N + 1) // 4:
			right = mid
		else:
			left = mid
	print(right)
main()


import math
n = int(input())
a = [int(i) for i in input().split(' ')]
m = n * (n + 1) // 2

class BIT:

	def __init__(self, n):
		self.t = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.t[i]
			i -= i & -i
		return s

	def add(self, i, v):
		while i < len(self.t):
			self.t[i] += v
			i += i & -i

def count(s):
	s_min = min(s)
	b = BIT(max(s) - s_min + 1)
	t = [0] * len(s)
	for j in range(0, len(s)):
		t[j] = b.sum(s[j] - s_min + 1)
		b.add(s[j] - s_min + 1, 1)
	return sum(t)

def bs(l, r):
	if l == r:
		return l
	else:
		h = math.ceil((l + r) / 2)
		ab = [-1 if a[i] < h else 1 for i in range(0, n)]
		s = [0] * (n + 1)
		for i in range(1, n + 1):
			s[i] = s[i - 1] + ab[i - 1]
		if count(s) >= math.ceil(m / 2):
			return bs(h, r)
		else:
			return bs(l, h - 1)
print(bs(min(a), max(a)))


def f(n, a):
	x = list(sorted(set(a)))
	n_sub_half = n * (n + 1) // 2 // 2
	n_plus_minus = n * 2 + 1
	Li = 0
	Ri = len(x)
	while Ri > Li + 1:
		i = (Li + Ri) // 2
		xi = x[i]
		cnt_sum = [0] * n_plus_minus
		cumsum = 0
		cnt_sum[cumsum] = 1
		judge = 0
		s = 0
		for ak in a:
			if ak >= xi:
				cumsum += 1
				s += cnt_sum[cumsum] + 1
			else:
				cumsum -= 1
				s -= cnt_sum[cumsum + 1] - 1
			cnt_sum[cumsum] += 1
			judge += s
			if judge >= n_sub_half:
				Li = i
				break
		else:
			Ri = i
	print(x[Li])
n = int(input())
a = list(map(int, input().split()))
f(n, a)


from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10 ** 5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right

def LI():
	return list(map(int, stdin.readline().split()))

def LF():
	return list(map(float, stdin.readline().split()))

def LI_():
	return list(map(lambda x: int(x) - 1, stdin.readline().split()))

def II():
	return int(stdin.readline())

def IF():
	return float(stdin.readline())

def LS():
	return list(map(list, stdin.readline().split()))

def S():
	return list(stdin.readline().rstrip())

def IR(n):
	return [II() for _ in range(n)]

def LIR(n):
	return [LI() for _ in range(n)]

def FR(n):
	return [IF() for _ in range(n)]

def LFR(n):
	return [LI() for _ in range(n)]

def LIR_(n):
	return [LI_() for _ in range(n)]

def SR(n):
	return [S() for _ in range(n)]

def LSR(n):
	return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

def A():
	(n, i) = LI()
	print(n - i + 1)
	return

def B():
	(h, w) = LI()
	a = SR(h)
	dy = defaultdict(int)
	dx = defaultdict(int)
	for y in range(h):
		for x in range(w):
			if a[y][x] == '#':
				dx[x] = 1
				dy[y] = 1
	dy = list(sorted(dy.items(), key=lambda x: x[0]))
	dx = list(sorted(dx.items(), key=lambda x: x[0]))
	for (y, _) in dy:
		for (x, _) in dx:
			print(a[y][x], end='')
		print()
	return

def C():
	(n, k) = LI()
	x = LI()
	ans = inf
	for i in range(n - k + 1):
		if x[i] * x[i + k - 1] > 0:
			ans = min(ans, max(abs(x[i]), abs(x[i + k - 1])))
			continue
		ans = min(ans, min(abs(x[i]), abs(x[i + k - 1])) * 2 + max(abs(x[i]), abs(x[i + k - 1])))
	print(ans)
	return

def D():

	class BinaBinaryIndexedTree:

		def __init__(self, size):
			self.bit = [0 for _ in range(size)]
			self.size = size

		def add(self, i, w):
			x = i + 1
			while x <= self.size:
				self.bit[x - 1] += w
				x += x & -x
			return

		def sum(self, i):
			res = 0
			x = i + 1
			while x > 0:
				res += self.bit[x - 1]
				x -= x & -x
			return res

		def __len__(self):
			return self.size

	def count_inversions(array, Max=None):
		if not Max:
			Max = max(array) + n
		bit = BinaBinaryIndexedTree(Max + 1)
		res = 0
		for i in range(len(array)):
			res += i - bit.sum(array[i])
			bit.add(array[i], 1)
		return res

	def f(i):
		x = a_sorted[i]
		c = [n] + [1 if e >= x else -1 for e in a]
		for i in range(n):
			c[i + 1] += c[i]
		tmp = count_inversions(c, 2 * n)
		if invmax - tmp >= (invmax + 1) // 2:
			return True
		else:
			return False
	n = II()
	a = LI()
	a_sorted = sorted(a)
	invmax = (n + 1) * n // 2
	ok = 0
	ng = n
	while abs(ok - ng) > 1:
		mid = (ok + ng) // 2
		if f(mid):
			ok = mid
		else:
			ng = mid
	print(a_sorted[ok])
	return
D()


def bisect_right_callable(fn, x, lo, hi):
	while lo < hi:
		mid = (lo + hi) // 2
		if x < fn(mid):
			hi = mid
		else:
			lo = mid + 1
	return lo
N = int(input())
series = list(map(int, input().split()))
series_sorted = sorted(series)
lr_size = (N + 1) * N / 2

def count_lr(x):
	ret = 0
	cumsum = 0
	counts = {i: 0 for i in range(-N, N + 1)}
	counts[cumsum] = 1
	diff = 0
	for i in range(N):
		if series[i] >= x:
			cumsum += 1
			counts[cumsum] += 1
			diff += counts[cumsum]
		else:
			cumsum -= 1
			counts[cumsum] += 1
			diff -= counts[cumsum + 1] - 1
		ret += diff
	return ret

def solve(i):
	if count_lr(series_sorted[i]) >= (lr_size + 1) // 2:
		return 0
	else:
		return float('inf')
ans_i = bisect_right_callable(solve, 0, lo=0, hi=N)
print(series_sorted[max(0, min(N - 1, ans_i - 1))])


N = int(input())
A = list(map(int, input().split()))
data = [0] * (N + 1)

def add(k, x, M):
	while k <= M:
		data[k] += x
		k += k & -k

def get(k):
	s = 0
	while k > 0:
		s += data[k]
		k -= k & -k
	return s
(left, right) = (0, 10 ** 9 + 1)
while right - left > 1:
	x = (left + right) // 2
	S = [0] * (N + 1)
	for i in range(N):
		if A[i] >= x:
			S[i + 1] = S[i] + 1
		else:
			S[i + 1] = S[i] - 1
	a = abs(min(S)) + 1
	for i in range(N + 1):
		S[i] += a
	b = max(S)
	data = [0] * (b + 1)
	num = 0
	for i in S:
		num += get(i)
		add(i, 1, b)
	if num * 2 >= N * (N + 1) // 2:
		left = x
	else:
		right = x
print(left)


def main():

	def add(i, x):
		while i <= size:
			tree[i] += x
			i += i & -i
	(n, *a) = map(int, open(0).read().split())
	size = n - ~n
	m = n * -~n // 2 + 1 >> 1
	ng = max(a) + 1
	ok = 0
	while ng - ok > 1:
		mid = ok + ng >> 1
		tree = [0] * -~size
		c = n + 1
		s = 0
		add(c, 1)
		for t in a:
			c += 1 if t >= mid else -1
			i = c
			while i:
				s += tree[i]
				i -= i & -i
			add(c, 1)
		if s >= m:
			ok = mid
		else:
			ng = mid
	print(ok)
main()


class BIT:

	def __init__(self, N):
		self.size = N
		self.tree = [0] * (N + 1)
		self.depth = n.bit_length()

	def _bitsum(self, i):
		ret = 0
		while i:
			ret += self.tree[i]
			i ^= i & -i
		return ret

	def bitsum(self, l, r=None):
		if r is None:
			return self._bitsum(l)
		else:
			return self._bitsum(r) - self._bitsum(l)

	def bitadd(self, i, x):
		i += 1
		while i <= self.size:
			self.tree[i] += x
			i += i & -i
		return
n = int(input())
m = n * (n + 1) // 4
a = list(map(int, input().split()))
d = dict()
_a = sorted(set(a + [0]))
for (i, x) in enumerate(_a):
	d[x] = i
a = [d[x] for x in a]

def check(X):
	b = [0] + [(y >= X) * 2 - 1 for y in a]
	for i in range(n):
		b[i + 1] += b[i]
	c = min(b)
	b = [x - c for x in b]
	bit = BIT(max(b) + 2)
	ans = 0
	for x in b:
		ans += bit.bitsum(x + 1)
		bit.bitadd(x, 1)
	return ans >= m
t = [len(_a), 0]
while t[0] - t[1] > 1:
	mid = (t[0] + t[1]) // 2
	t[check(mid)] = mid
print(_a[t[1]])


def main():
	from itertools import accumulate as ac
	n = int(input())
	a = list(map(int, input().split()))

	class BIT:

		def __init__(self, n):
			self.n = n
			self.bit = [0] * (n + 1)

		def add(self, i, v):
			x = i + 1
			while x < self.n + 1:
				self.bit[x] += v
				x += x & -x

		def sum(self, i):
			ret = 0
			x = i
			while x > 0:
				ret += self.bit[x]
				x -= x & -x
			return ret

		def sum_range(self, i, j):
			return self.sum(j) - self.sum(i)

	def value(v):
		if n == 1:
			if v <= a[0]:
				return True
			else:
				return False
		b = [0] + list(ac([(i >= v) * 2 - 1 for i in a]))
		bit = BIT(2 * n + 1)
		ans = 0
		bit.add(b[-1] + n, 1)
		for i in range(n - 1, -1, -1):
			w = b[i]
			ans += bit.sum_range(w + n, 2 * n + 1)
			bit.add(w + n, 1)
		if ans >= n * (n + 1) // 2 // 2:
			return True
		else:
			return False

	def b_search(ok, ng, value):
		while abs(ok - ng) > 1:
			mid = (ok + ng) // 2
			if value(mid):
				ok = mid
			else:
				ng = mid
		return ok
	print(b_search(0, 10 ** 9 + 1, value))
main()


class imosBIT:

	def __init__(self, N):
		self.N = N
		self.bit = [0 for _ in range(self.N + 1)]

	def __str__(self):
		ret = []
		for i in range(1, self.N + 1):
			ret.append(self.__getitem__(i))
		return '[' + ', '.join([str(a) for a in ret]) + ']'

	def __getitem__(self, i):
		s = 0
		while i > 0:
			s += self.bit[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.N:
			self.bit[i] += x
			i += i & -i
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
l = 0
r = max(A) + 1
while r - l > 1:
	x = (l + r) // 2
	P = [0]
	for a in A:
		p = +1 if a >= x else -1
		P.append(P[-1] + p)
	score = 0
	bit = imosBIT(2 * N + 5)
	for p in P:
		p += N + 1
		score += bit[p]
		bit.add(p, 1)
	if score >= (N * (N + 1) // 2 + 1) // 2:
		l = x
	else:
		r = x
print(l)


n = int(input())
a = list(map(int, input().split()))
if n == 1:
	print(a[0])
	exit()
b = list(sorted(set(a)))

def count_inversion(ans):
	s = [0 for _ in range(2 * n + 2)]

	def bit_add(i):
		x = i
		while x < 2 * n:
			s[x] += 1
			x += x & -x

	def bit_sum(i):
		x = i
		ret = 0
		while x > 0:
			ret += s[x]
			x -= x & -x
		return ret
	temp = [n for _ in range(n + 1)]
	temp[0] = n + 1
	for i in range(n):
		if a[i] >= b[ans]:
			temp[i + 1] = temp[i] + 1
		else:
			temp[i + 1] = temp[i] - 1
	res = 0
	for i in range(n + 1):
		x = temp[i]
		res += bit_sum(x)
		bit_add(x)
	return res
m = n * (n + 1) // 2
ans = 0
l = 0
r = len(b)
while 1:
	ans = (l + r) // 2
	if count_inversion(ans) * 2 >= m:
		l = ans
	else:
		r = ans
	if r - l <= 1:
		ans = l
		break
print(b[ans])


N = int(input())
A = [int(x) for x in input().split()]
total_medians = N * (N + 1) // 2

def BIT_update(BIT, x, value):
	L = len(BIT)
	while x < L:
		BIT[x] += value
		bottom_bit = x & -x
		x += bottom_bit
	return

def BIT_sum(BIT, x):
	result = 0
	while x:
		result += BIT[x]
		bottom_bit = x & -x
		x -= bottom_bit
	return result

def test(x):
	B = [0]
	for a in A:
		B.append(B[-1] + (1 if a > x else -1))
	m = min(B) - 1
	B = [x - m for x in B]
	BIT = [0] * (N + 1)
	cnt = 0
	for R in range(1, N + 1):
		BIT_update(BIT, B[R - 1], 1)
		cnt += BIT_sum(BIT, B[R])
	return cnt <= (total_medians - 1) // 2
AA = sorted(A)
left = -1
right = len(AA) - 1
while right - left > 1:
	mid = (left + right) // 2
	if test(AA[mid]):
		right = mid
	else:
		left = mid
answer = AA[right]
print(answer)


from bisect import bisect_left
from math import ceil
import sys
if sys.version_info[0:2] >= (3, 3):
	from collections.abc import Sequence
else:
	from collections import Sequence

class LazySequence(Sequence):

	def __init__(self, f, n):
		self.f = f
		self.n = n

	def __len__(self):
		return self.n

	def __getitem__(self, i):
		if not 0 <= i < self.n:
			raise IndexError
		return self.f(i)

class Bit:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)

	def __len__(self):
		return self.size

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, v):
		while i <= self.size:
			self.tree[i] += v
			i += i & -i
N = int(input())
a = [0] + [int(s) for s in input().split()]

def count_lr(x):
	s = [0] * (N + 1)
	for i in range(1, N + 1):
		s[i] = s[i - 1] + (1 if a[i] >= x else -1)
	ss = sorted(set(s))
	ind = {v: i + 1 for (i, v) in enumerate(ss)}
	b = Bit(N + 10)
	count = 0
	for i in range(N + 1):
		j = ind[s[i]]
		count += b.sum(j)
		b.add(j, 1)
	return count
counts = LazySequence(lambda i: count_lr(10 ** 9 - i), 10 ** 9 + 1)
ans = 10 ** 9 - bisect_left(counts, ceil(N * (N + 1) / 4))
print(ans)


from itertools import combinations
from math import ceil
N = int(input())
A = list(map(int, input().split()))
M = ceil(N * (N + 1) / 4)

class FenwickTree(object):

	def __init__(self, n):
		self._bit = [0] * (n + 1)
		self.n = n + 1

	def add(self, i, a):
		i += 1
		while i < self.n:
			self._bit[i] += a
			i += i & -i

	def sum(self, i):
		i += 1
		ret = 0
		while i > 0:
			ret += self._bit[i]
			i -= i & -i
		return ret
(lo, hi) = (0, max(A) + 1)
while lo < hi - 1:
	mid = (lo + hi) // 2
	B = [1 if a >= mid else -1 for a in A]
	C = []
	C.append(0)
	for b in B:
		C.append(C[-1] + b)
	cmin = min(C)
	for i in range(N + 1):
		C[i] -= cmin
	cmax = max(C) + 1
	fw = FenwickTree(cmax)
	cnt = 0
	for i in range(N + 1):
		cnt += fw.sum(C[i])
		fw.add(C[i], 1)
	if cnt >= M:
		lo = mid
	else:
		hi = mid
print(lo)


def mergecount(A):
	cnt = 0
	n = len(A)
	if n > 1:
		A1 = A[:n >> 1]
		A2 = A[n >> 1:]
		cnt += mergecount(A1)
		cnt += mergecount(A2)
		i1 = 0
		i2 = 0
		for i in range(n):
			if i2 == len(A2):
				A[i] = A1[i1]
				i1 += 1
			elif i1 == len(A1):
				A[i] = A2[i2]
				i2 += 1
			elif A1[i1] <= A2[i2]:
				A[i] = A1[i1]
				i1 += 1
			else:
				A[i] = A2[i2]
				i2 += 1
				cnt += n // 2 - i1
	return cnt
n = int(input())
l = [int(_) for _ in input().split()]
p = (n * n + n) / 2
q = 0
if p % 2 == 0:
	q = p // 2
else:
	q = p // 2 + 1
l_set = list(set(l))
l_sorted = sorted(l_set)
ans = 0
l_t = [0 for _ in range(n)]
s = [0 for _ in range(n + 1)]
low = 0
high = len(l_sorted) - 1
while low <= high:
	mid = (low + high) // 2
	m = l_sorted[mid]
	for j in range(n):
		if l[j] < m:
			l_t[j] = -1
		else:
			l_t[j] = 1
	for k in range(n):
		s[k + 1] = s[k] + l_t[k]
	x = mergecount(s)
	if p - x >= q:
		low = mid + 1
		ans = max(m, ans)
	else:
		high = mid - 1
print(ans)


def f(n, a):
	x = sorted(set(a))
	n_sub_half = n * (n + 1) // 2 // 2
	n1 = n * 2 + 1
	li = 0
	ri = len(x)
	while ri > li + 1:
		i = (li + ri) // 2
		xi = x[i]
		cnt = [0] * n1
		cs = 0
		cnt[cs] = 1
		judge = 0
		s = 0
		for ak in a:
			if ak >= xi:
				cs += 1
				s += cnt[cs] + 1
			else:
				cs -= 1
				s -= cnt[cs + 1] - 1
			cnt[cs] += 1
			judge += s
			if judge >= n_sub_half:
				li = i
				break
		else:
			ri = i
	return x[li]
n = int(input())
ar = [int(i) for i in input().strip().split(' ')]
print(f(n, ar))


from itertools import accumulate
from math import ceil
N = int(input())
A = list(map(int, input().split()))
if N == 1:
	print(A[0])
	exit()

class BinaryIndexedTree:

	def __init__(self, n):
		self.size = n
		self.bit = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.bit[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.bit[i] += x
			i += i & -i

	def reset(self):
		self.bit = [0] * (self.size + 1)
BIT = BinaryIndexedTree(N)
(lo, hi) = (-1, 10 ** 9 + 1)
while hi - lo > 1:
	X = (hi + lo) // 2
	Binary = [1 if a >= X else -1 for a in A]
	Binary = list(accumulate(Binary))
	BIT.reset()
	inversion = 0
	Binary_sorted = {b: i for (i, b) in enumerate(sorted(Binary), start=1)}
	for (j, b) in enumerate(Binary):
		inversion += BIT.sum(Binary_sorted[b]) + (b >= 0)
		BIT.add(Binary_sorted[b], 1)
	if inversion >= ceil(N * (N + 1) / 2 / 2):
		lo = X
	else:
		hi = X
print(lo)


def median_of_medians(N: int, A: list) -> int:

	def search(c):
		bar = N
		r = 0
		res_nega = 0
		dp_arr = [0] * (2 * N + 1)
		for i in range(N):
			dp_arr[bar] += 1
			if A[i] < c:
				r += dp_arr[bar]
				bar += 1
			else:
				r -= dp_arr[bar - 1]
				bar -= 1
			res_nega += r
		return res_nega
	a_sorted = sorted(A)
	left = 0
	right = N
	mid = N // 2
	C = N * (N + 1) // 2
	while True:
		if search(a_sorted[mid]) <= C // 2:
			if mid == N - 1:
				break
			elif search(a_sorted[mid + 1]) > C // 2:
				break
			else:
				left = mid
				mid = (mid + right) // 2
		else:
			right = mid + 1
			mid = (mid + left) // 2
	return a_sorted[mid]

def __starting_point():
	N = int(input())
	A = [int(s) for s in input().split()]
	ans = median_of_medians(N, A)
	print(ans)
__starting_point()


import sys
try:
	from typing import List
except ImportError:
	pass

class BIT:

	def __init__(self, n: int):
		self.tr = [0] * (n + 1)

	def add(self, n: int, v: int):
		while n < len(self.tr):
			self.tr[n] += v
			n += n & -n

	def cumsum(self, n: int):
		ans = 0
		while n > 0:
			ans += self.tr[n]
			n -= n & -n
		return ans

def solve(N: int, a: 'List[int]'):

	def f(m):
		s = [0] * (N + 1)
		for (i, ai) in enumerate(a):
			s[i + 1] = s[i] + (-1 if ai < m else 1)
		ms = min(s)
		b = BIT(max(s) - ms + 1)
		t = 0
		for si in s:
			t += b.cumsum(si - ms + 1)
			b.add(si - ms + 1, 1)
		return t >= -(-(N * (N + 1) // 2) // 2)
	lb = 0
	rb = max(a) + 1
	while lb + 1 < rb:
		m = (lb + rb) // 2
		if f(m):
			lb = m
		else:
			rb = m
	print(lb)

def main():

	def iterate_tokens():
		for line in sys.stdin:
			for word in line.split():
				yield word
	tokens = iterate_tokens()
	N = int(next(tokens))
	a = [int(next(tokens)) for _ in range(N)]
	solve(N, a)
main()


import sys
sys.setrecursionlimit(10 ** 6)
readline = sys.stdin.readline
n = int(input())
a = [int(i) for i in readline().split()]

def binarysearch(ok, ng, isOK):
	while abs(ok - ng) > 1:
		mid = (ok + ng) // 2
		if isOK(mid):
			ok = mid
		else:
			ng = mid
	return ok
from collections import Counter

def isOK(x):
	c = [1 if i >= x else -1 for i in a]
	res = Counter([0])
	now = 0
	less = 1
	ans = 0
	for i in range(n):
		if c[i] > 0:
			less += res[now + 1]
		else:
			less -= res[now]
		now += c[i]
		ans += less
		less += 1
		res[now] += 1
	return ans >= (n * (n + 1) // 2 + 1) // 2
ans = binarysearch(0, 10 ** 9 + 1, isOK)
print(ans)


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string
INF = float('inf')

def LI():
	return list(map(int, sys.stdin.readline().split()))

def I():
	return int(sys.stdin.readline())

def LS():
	return sys.stdin.readline().split()

def S():
	return sys.stdin.readline().strip()

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]

def SRL(n):
	return [list(S()) for i in range(n)]

def MSRL(n):
	return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7
n = I()
A = LI()

class BIT:

	def __init__(self, size):
		self.bit = [0] * size
		self.size = size

	def add(self, i, w):
		x = i + 1
		while x <= self.size:
			self.bit[x - 1] += w
			x += x & -x
		return

	def sum(self, i):
		res = 0
		x = i + 1
		while x > 0:
			res += self.bit[x - 1]
			x -= x & -x
		return res

def D(L):
	n = len(L)
	bit = BIT(2 * n + 1)
	ans = 0
	for i in range(n - 1, -1, -1):
		bit.add(L[i] + n, 1)
		ans += bit.sum(L[i] + n - 1)
	return ans
ALL = (n + 1) * n // 2
A2 = sorted(A)
(ng, ok) = (n, 0)
while ng > ok + 1:
	mid = (ok + ng) // 2
	L = [0] + list(accumulate([1 if i >= A2[mid] else -1 for i in A]))
	if D(L) >= ALL // 2 + 1:
		ng = mid
	else:
		ok = mid
print(A2[ok])


N = int(input())
A = list(map(int, input().split()))

class BIT:

	def __init__(self, n):
		self.n = n
		self.data = [0] * n

	def add(self, k, x):
		while k < self.n:
			self.data[k] += x
			k += k & -k

	def get(self, k):
		s = 0
		while k > 0:
			s += self.data[k]
			k -= k & -k
		return s

	def init(self, n):
		self.n = n
		self.data = [0] * n
(left, right) = (0, 10 ** 9 + 5)
bit = BIT(N)
while right - left > 1:
	x = (right + left) // 2
	S = [0] * (N + 1)
	for i in range(N):
		if A[i] >= x:
			S[i + 1] = S[i] + 1
		else:
			S[i + 1] = S[i] - 1
	p = abs(min(S)) + 1
	for i in range(N + 1):
		S[i] += p
	q = max(S) + 1
	bit.init(q)
	num = 0
	for i in S:
		num += bit.get(i)
		bit.add(i, 1)
	if num * 2 >= N * (N + 1) // 2:
		left = x
	else:
		right = x
print(left)


from itertools import accumulate

class BIT:

	def __init__(self, size):
		self.bit = [0] * (size + 1)
		self.size = size

	def sum(self, i):
		i += 1
		s = 0
		while i > 0:
			s += self.bit[i]
			i -= i & -i
		return s

	def add(self, i, x):
		i += 1
		while i <= self.size:
			self.bit[i] += x
			i += i & -i
N = int(input())
a = list(map(int, input().split()))
(lb, ub) = (-1, 10 ** 9)
while ub - lb > 1:
	m = (lb + ub) // 2
	b = [0] * (N + 1)
	for i in range(N):
		if a[i] <= m:
			b[i + 1] = 1
	b = list(accumulate(b))
	bit_odd = BIT(2 * N)
	bit_even = BIT(2 * N)
	cnt = 0
	for i in range(N):
		x = N + b[i + 1] - i // 2 - 1
		y = N + b[i + 1] - (i + 1) // 2 - 1
		if i % 2 == 0:
			bit_even.add(N + b[i] - i // 2, 1)
			cnt += bit_even.sum(x) + bit_odd.sum(y)
		else:
			bit_odd.add(N + b[i] - i // 2, 1)
			cnt += bit_even.sum(y) + bit_odd.sum(x)
	if cnt < N * (N + 1) // 4 + 1:
		lb = m
	else:
		ub = m
print(ub)


def d_median_of_medians(N, A):

	class BIT(object):

		def __init__(self, n):
			self.size = n
			self.tree = [0] * (n + 1)

		def sum(self, index):
			ret = 0
			while index > 0:
				ret += self.tree[index]
				index -= index & -index
			return ret

		def add(self, index, value):
			while index <= self.size:
				self.tree[index] += value
				index += index & -index

	def is_accepted(x):
		from itertools import accumulate
		from math import ceil
		a_larger_x = [1 if a >= x else -1 for a in A]
		cumsum = list(accumulate(a_larger_x))
		ans = 0
		a_larger_x_sorted = {a: k for (k, a) in enumerate(sorted(cumsum), 1)}
		bit = BIT(N)
		for c in cumsum:
			ans += bit.sum(a_larger_x_sorted[c]) + int(c >= 0)
			bit.add(a_larger_x_sorted[c], 1)
		return True if ans >= ceil(N * (N + 1) / 4) else False
	accept = 0
	reject = 10 ** 9 + 1
	while reject - accept > 1:
		mid = (accept + reject) // 2
		if is_accepted(mid):
			accept = mid
		else:
			reject = mid
	return accept
N = int(input())
A = [int(i) for i in input().split()]
print(d_median_of_medians(N, A))


N = int(input())
a = [int(x) for x in input().split()]
b = sorted(a)
M = ((N + 1) * N // 2 + 1) // 2

class BIT(object):

	def __init__(self, N=1):
		self.N = N
		self.bit = [0] * (N + 1)

	def add(self, i, x):
		while i <= self.N:
			self.bit[i] += x
			i += i & -i

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.bit[i]
			i -= i & -i
		return s

def is_OK(x):
	S = [1] * N
	for i in range(N):
		if a[i] < x:
			S[i] = -1
		if i > 0:
			S[i] += S[i - 1]
	S = [0] + S
	min_S = min(S)
	max_S = max(S)
	bit = BIT(max_S - min_S + 1)
	cnt = 0
	for S_i in S:
		S_i = S_i - min_S + 1
		cnt += bit.sum(S_i)
		bit.add(S_i, 1)
	return cnt >= M
(left, right) = (0, 10 ** 9 + 1)
while right - left > 1:
	mid = (left + right) // 2
	if is_OK(mid):
		left = mid
	else:
		right = mid
print(left)


N = int(input())
A = list(map(int, input().split()))
sortA = sorted(set(A)) + [float('inf')]

def isOk(n):
	x = sortA[n]
	count = [0 for _ in range(2 * N + 1)]
	count[N + 1] = 1
	i = N + 1
	s = 1
	result = 0
	for a in A:
		if a >= x:
			i += 1
			s += count[i]
		else:
			s -= count[i]
			i -= 1
		result += s
		count[i] += 1
		s += 1
	if result >= N * (N + 1) // 4:
		return False
	else:
		return True
left = 0
right = len(sortA) - 1
while right - left > 1:
	mid = (left + right) // 2
	if isOk(mid):
		right = mid
	else:
		left = mid
print(sortA[left])


import sys
from itertools import accumulate

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST():
	return list(map(int, input().split()))

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class BIT:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)

	def sum(self, i):
		s = 0
		i += 1
		while i > 0:
			s += self.tree[i - 1]
			i -= i & -i
		return s

	def add(self, i, x):
		i += 1
		while i <= self.size:
			self.tree[i - 1] += x
			i += i & -i
N = INT()
A = LIST()
ALL = (N + 1) * N // 2

def get_inv(A):
	N = len(A)
	bit = BIT(N * 2 + 1)
	ans = 0
	for i in range(N - 1, -1, -1):
		bit.add(A[i] + N, 1)
		ans += bit.sum(A[i] + N - 1)
	return ans

def calc(X):
	L = [0] * N
	for i in range(N):
		if A[i] >= X:
			L[i] = 1
		else:
			L[i] = -1
	sm = [0] + list(accumulate(L))
	ans = ALL - get_inv(sm)
	return ans >= ceil(ALL, 2)
A2 = sorted(set(A))
low = 0
hi = len(A2)
while low + 1 < hi:
	mid = (hi + low) // 2
	if calc(A2[mid]):
		low = mid
	else:
		hi = mid
print(A2[low])


import sys
sys.setrecursionlimit(2147483647)
INF = float('inf')
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()
import sys
sys.setrecursionlimit(2147483647)
INF = float('inf')
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()

class BIT(object):

	def __init__(self, A, dot=lambda x, y: x + y, e=0, inv=None):
		n = len(A)
		self.__n = n
		self.__dot = dot
		self.__e = e
		self.__inv = inv
		self.__node = ['$'] + A
		for i in range(1, n + 1):
			j = i + (i & -i)
			if j <= n:
				self.__node[j] = dot(self.__node[i], self.__node[j])

	def add(self, i, w=1):
		i += 1
		while i <= self.__n:
			self.__node[i] = self.__dot(self.__node[i], w)
			i += i & -i

	def sum(self, i):
		res = self.__e
		while i > 0:
			res = self.__dot(res, self.__node[i])
			i -= i & -i
		return res

def bisection(l, r, f, left=True, discrete=True):
	eps = 1 if discrete else 10 ** (-12)
	if (not left) ^ f(r):
		return r if left else r + 1
	elif left ^ f(l):
		return l - 1 if left else l
	while r - l > eps:
		h = (l + r) // 2 if discrete else (l + r) / 2
		if (not left) ^ f(h):
			l = h
		else:
			r = h
	return (l + r) / 2 if not discrete else l if left else r

def resolve():
	n = int(input())
	A = list(map(int, input().split()))
	M = max(A)

	def check(x):
		B = [1 if a >= x else -1 for a in A]
		S = [0] * (n + 1)
		for i in range(n):
			S[i + 1] = S[i] + B[i]
		D = {d: i for (i, d) in enumerate(sorted(set(S)))}
		for i in range(n + 1):
			S[i] = D[S[i]]
		cnt = 0
		bit = BIT([0] * (n + 1))
		for i in range(n + 1):
			cnt += bit.sum(S[i] + 1)
			bit.add(S[i])
		return cnt * 2 >= n * (n + 1) // 2
	print(bisection(0, M, check))
resolve()


N = int(input())
(*A,) = map(int, input().split())

def solve(x):
	data = [0] * (N + 1)

	def add(k, x):
		while k <= N:
			data[k] += x
			k += k & -k

	def get(k):
		s = 0
		while k:
			s += data[k]
			k -= k & -k
		return s
	c = 0
	d = 10 ** 18
	for a in A:
		if x <= a:
			c += 1
		else:
			c -= 1
		d = min(c, d)
	res = N * (N + 1) // 2
	c = -d + 1
	for a in A:
		res -= get(c)
		if x <= a:
			c += 1
		else:
			c -= 1
		add(c, 1)
	return res <= N * (N + 1) // 4
left = min(A)
right = max(A) + 1
while left + 1 < right:
	mid = (left + right) // 2
	if solve(mid):
		left = mid
	else:
		right = mid
print(left)


class BIT:

	def __init__(self, n):
		self.bit = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.bit[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i < len(self.bit):
			self.bit[i] += x
			i += i & -i
N = int(input())
a = list(map(int, input().split()))

def ans_bigger(X):
	a_X = [1 if a[i] >= X else -1 for i in range(N)]
	cum = [N]
	for i in range(N):
		cum.append(cum[i] + a_X[i])
	b = BIT(2 * N + 1)
	ans = 0
	for j in range(N + 1):
		ans += b.sum(cum[j])
		b.add(cum[j], 1)
	if ans >= ((N + 1) * N / 2 + 1) // 2:
		return True
	else:
		return False
l = min(a)
r = max(a) + 1
while r > l + 1:
	if ans_bigger((l + r) // 2):
		l = (l + r) // 2
	else:
		r = (l + r) // 2
print(l)


import sys
input = sys.stdin.readline

def I():
	return int(input())

def MI():
	return map(int, input().split())

def LI():
	return list(map(int, input().split()))

def main():

	class BIT:

		def __init__(self, N):
			self.size = N
			self.tree = [0] * (N + 1)
			self.depth = N.bit_length()

		def _bitsum(self, i):
			ret = 0
			while i:
				ret += self.tree[i]
				i ^= i & -i
			return ret

		def sum(self, l, r=None):
			if r is None:
				return self._bitsum(l)
			else:
				return self._bitsum(r) - self._bitsum(l)

		def add(self, i, x):
			i += 1
			while i <= self.size:
				self.tree[i] += x
				i += i & -i
			return

		def lower_bound(self, x):
			sum_ = 0
			pos = 0
			v = 1 << self.depth
			for i in range(self.depth, -1, -1):
				k = pos + v
				if k <= self.size and sum_ + self.tree[k] < x:
					sum_ += self.tree[k]
					pos += v
				v >>= 1
			return (pos + 1, sum_)
	N = I()
	A = LI()

	def calc(x):
		B = [0] * N
		for i in range(N):
			if A[i] >= x:
				B[i] = 1
			else:
				B[i] = -1
		S = [0] * (N + 1)
		for i in range(N):
			S[i + 1] = S[i] + B[i]
		inf = 10 ** 6
		for i in range(N + 1):
			S[i] = S[i] * inf + i
		S.sort()
		bit = BIT(N + 1)
		res = 0
		for i in range(N + 1):
			s = S[i]
			ii = s % inf
			temp = bit.sum(0, ii)
			res += temp
			bit.add(ii, 1)
		return res
	A2 = sorted(A)
	M = N * N // 2
	ok = 0
	ng = N

	def ch(x):
		cnt = calc(x)
		return cnt >= (M + 1) // 2
	while ng - ok > 1:
		med = (ok + ng) // 2
		x = A2[med]
		if ch(x):
			ok = med
		else:
			ng = med
	print(A2[ok])
main()


n = int(input())
A = list(map(int, input().split()))

class Bit:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.tree[i] += x
			i += i & -i
le = -1
ri = max(A) + 1
mid = (le + ri) // 2
while ri - le > 1:
	S = [0] * n
	S[0] = -1 + 2 * int(A[0] >= mid)
	for i in range(n - 1):
		S[i + 1] = S[i] - 1 + 2 * int(A[i + 1] >= mid)
	bit = Bit(n + 2)
	ans = 0
	for i in range(n):
		if S[i] >= 0:
			ans += 1
	Smin = min(S)
	S = [S[i] - Smin + 1 for i in range(n)]
	for (i, p) in enumerate(S):
		bit.add(p, 1)
		ans += bit.sum(p) - 1
	if ans >= n * (n + 1) // (2 * 2):
		le = mid
	else:
		ri = mid
	mid = (le + ri) // 2
print(le)


class Bit:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.tree[i] += x
			i += i & -i

def invnumber(n, S):
	bit = Bit(2 * n + 1)
	invs = 0
	for i in range(n):
		s = S[i] + n
		invs += bit.sum(s)
		bit.add(s, 1)
	return invs
n = int(input())
a = list(map(int, input().split()))
r = max(a) + 1
l = 0
c = (n * (n + 1) // 2 + 1) // 2
while r - l > 1:
	m = (l + r) // 2
	S = [0] * (n + 1)
	for i in range(1, n + 1):
		if a[i - 1] >= m:
			S[i] = S[i - 1] + 1
		else:
			S[i] = S[i - 1] - 1
	if invnumber(n + 1, S) >= c:
		l = m
	else:
		r = m
print(l)


import sys
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()
YesNo = lambda b: bool([print('Yes')] if b else print('No'))
YESNO = lambda b: bool([print('YES')] if b else print('NO'))
int1 = lambda x: int(x) - 1

def main():
	N = int(input())
	a = list(map(int, input().split()))

	class BIT:

		def __init__(self, n):
			self.num = n
			self.dat = [0] * (self.num + 1)
			self.depth = n.bit_length()

		def add(self, i, x):
			i += 1
			while i <= self.num:
				self.dat[i] += x
				i += i & -i

		def sum(self, i):
			i += 1
			s = 0
			while i > 0:
				s += self.dat[i]
				i -= i & -i
			return s

		def lower_bound(self, x):
			sum_ = 0
			pos = 0
			for i in range(self.depth, -1, -1):
				k = pos + (1 << i)
				if k <= self.num and sum_ + self.dat[k] < x:
					sum_ += self.dat[k]
					pos += 1 << i
			return (pos, sum_)

	def nibutan(ok, ng):
		while abs(ok - ng) > 1:
			mid = (ok + ng) // 2
			if solve(mid):
				ok = mid
			else:
				ng = mid
		return ok

	def solve(mid):
		aa = [1 if x >= mid else -1 for x in a]
		b = BIT(N * 2 + 1)
		c = 0
		s = N
		b.add(s, 1)
		for x in aa:
			s += x
			c += b.sum(s)
			b.add(s, 1)
		return c >= -(-N * (N + 1) // 2 // 2)
	print(nibutan(1, 10 ** 9 + 1))
main()


import sys
from itertools import accumulate
INF = float('inf')

class Bit:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.tree[i] += x
			i += i & -i

def inversion(a):
	d = {av: i + 1 for (i, av) in enumerate(sorted(a))}
	b = Bit(len(a))
	ans = 0
	for (i, av) in enumerate(a):
		ans += b.sum(d[av])
		b.add(d[av], 1)
	return ans

def solve(N: int, a: 'List[int]'):

	def isOK(y):
		acc = (1 if aa >= y else -1 for aa in a)
		acc = tuple([0]) + tuple(accumulate(acc))
		invs = inversion(acc)
		if acc[0] == -1:
			invs -= 1
		return invs < N * (N + 1) // 4

	def binary_search(x):
		ng = -1
		ok = len(x) + 1
		while abs(ok - ng) > 1:
			mid = (ok + ng) // 2
			if isOK(mid):
				ok = mid
			else:
				ng = mid
		return (ng, ok)
	(ng, ok) = binary_search(range(max(a)))
	print(ng)
	return

def main():

	def iterate_tokens():
		for line in sys.stdin:
			for word in line.split():
				yield word
	tokens = iterate_tokens()
	N = int(next(tokens))
	a = [int(next(tokens)) for _ in range(N)]
	solve(N, a)
main()


n = int(input())
a = list(map(int, input().split()))
sortA = sorted(set(a)) + [float('inf')]

def isOK(m):
	x = sortA[m]
	cnt = [0] * (2 * n + 1)
	cnt[n + 1] = 1
	i = n + 1
	s = 1
	res = 0
	for b in a:
		if b >= x:
			i += 1
			s += cnt[i]
		else:
			s -= cnt[i]
			i -= 1
		res += s
		cnt[i] += 1
		s += 1
	if res >= n * (n + 1) // 4:
		return False
	else:
		return True
(l, r) = (0, len(sortA) - 1)
while r - l > 1:
	mid = (r + l) // 2
	if isOK(mid):
		r = mid
	else:
		l = mid
print(sortA[l])


from itertools import accumulate
from math import ceil
N = int(input())
a = list(map(int, input().split()))

class BIT:

	def __init__(self, n):
		self.n = n
		self.bit = [0] * (n + 1)

	def update(self, i, v):
		while i <= self.n:
			self.bit[i] += v
			i += i & -i

	def query(self, i):
		ret = 0
		while i > 0:
			ret += self.bit[i]
			i -= i & -i
		return ret

	def reset(self):
		self.bit = [0] * (self.n + 1)
ub = max(a) + 1
lb = 0
th = ceil((N + 1) * N // 2 / 2)
bit = BIT(N + 1)
while ub - lb > 1:
	mid = (ub + lb) // 2
	b = [1 if v >= mid else -1 for v in a]
	b = [0] + list(accumulate(b))
	b_sorted = {v: i + 1 for (i, v) in enumerate(sorted(b))}
	cnt = 0
	bit.reset()
	for v in b:
		cnt += bit.query(b_sorted[v])
		bit.update(b_sorted[v], 1)
	if cnt >= th:
		lb = mid
	else:
		ub = mid
print(lb)


import math
n = int(input())
lst = list(map(int, input().split()))

class Bit:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.tree[i] += x
			i += i & -i

def judge(x, lst, n):
	length = len(lst)
	all_pair = length * (length - 1) // 2 + length
	lst_r = [-1 if i < x else 1 for i in lst]
	lst_accum = []
	a = 0
	for i in lst_r:
		a += i
		lst_accum.append(a)
	bit = Bit(n)
	lst_accum_sorted = {b: i for (i, b) in enumerate(sorted(lst_accum), start=1)}
	count = 0
	for (j, b) in enumerate(lst_accum):
		count += bit.sum(lst_accum_sorted[b]) + (b >= 0)
		bit.add(lst_accum_sorted[b], 1)
	if count >= math.ceil(all_pair / 2):
		return True
	else:
		return False
sorted_lst = sorted(lst)
low = 0
high = len(lst) - 1
while high - low > 1:
	t = (low + high) // 2
	i = sorted_lst[t]
	if judge(i, lst, n):
		low = t
	else:
		high = t
print(sorted_lst[high]) if judge(sorted_lst[high], lst, n) else print(sorted_lst[low])


from itertools import accumulate
from math import ceil
N = int(input())
A = list(map(int, input().split()))

class BinaryIndexedTree:

	def __init__(self, n):
		self.size = n
		self.bit = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.bit[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.bit[i] += x
			i += i & -i

	def reset(self):
		self.bit = [0] * (self.size + 1)
BIT = BinaryIndexedTree(N)
(lo, hi) = (-1, max(A) + 1)
while hi - lo > 1:
	m = (hi + lo) // 2
	binary = [1 if a >= m else -1 for a in A]
	binary = list(accumulate(binary))
	BIT.reset()
	tmp = 0
	binary_sorted = {b: i for (i, b) in enumerate(sorted(binary), start=1)}
	ans = 0
	for (j, b) in enumerate(binary):
		tmp += BIT.sum(binary_sorted[b]) + (b >= 0)
		BIT.add(binary_sorted[b], 1)
	if tmp >= ceil(N * (N + 1) / 2 / 2):
		lo = m
	else:
		hi = m
print(lo)


import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 5)

def li():
	return map(int, stdin.readline().split())

def li_():
	return map(lambda x: int(x) - 1, stdin.readline().split())

def lf():
	return map(float, stdin.readline().split())

def ls():
	return stdin.readline().split()

def ns():
	return stdin.readline().rstrip()

def lc():
	return list(ns())

def ni():
	return int(stdin.readline())

def nf():
	return float(stdin.readline())
from itertools import accumulate

class BIT(object):

	def __init__(self, size):
		self.size = size + 1
		self.bitree = [0] * self.size

	def addval(self, idx: int, val: int):
		while idx < self.size:
			self.bitree[idx] += val
			idx += idx & -idx

	def getsum(self, idx: int):
		ret = 0
		while idx > 0:
			ret += self.bitree[idx]
			idx -= idx & -idx
		return ret

	def reset(self):
		self.bitree = [0] * self.size

def findInv(arr: list, med: int):
	arrbin = [-1 if ai < med else 1 for ai in arr]
	arrcum = [0] + list(accumulate(arrbin))
	arrcummin = abs(min(arrcum))
	arrcumpos = [arrcum_i + arrcummin + 1 for arrcum_i in arrcum]
	bitree = BIT(max(arrcumpos))
	inv = 0
	for (i, ai) in enumerate(arrcumpos):
		inv += i - bitree.getsum(ai)
		bitree.addval(ai, 1)
	return inv

def binsearch(arr: list):
	low = 0
	high = max(arr) + 1
	n = len(arr)
	threshould = n * (n + 1) // 4
	while high - low > 1:
		mid = (high + low) // 2
		if findInv(arr, mid) <= threshould:
			low = mid
		else:
			high = mid
	return low
n = ni()
a = list(li())
print(binsearch(a))


n = int(input())
a = list(map(int, input().split()))

def check(x):
	b = n
	r = 0
	y = 0
	D = [0] * (2 * n + 1)
	for i in range(n):
		D[b] += 1
		if a[i] < x:
			r += D[b]
			b += 1
		else:
			b -= 1
			r -= D[b]
		y += r
	return y
alpha = sorted(a)
(l, r) = (0, n)
(m, c) = (n // 2, n * (n + 1) // 2)
while True:
	if check(alpha[m]) <= c // 2:
		if m == n - 1:
			break
		elif check(alpha[m + 1]) > c // 2:
			break
		else:
			(l, m) = (m, (m + r) // 2)
	else:
		(m, r) = ((m + l) // 2, m + 1)
print(alpha[m])


import sys
input = sys.stdin.readline
from collections import *

class BIT:

	def __init__(self, n):
		self.n = n
		self.bit = [0] * (n + 1)

	def add(self, i, x):
		i += 1
		while i <= self.n:
			self.bit[i] += x
			i += i & -i

	def acc(self, i):
		i += 1
		s = 0
		while i > 0:
			s += self.bit[i]
			i -= i & -i
		return s

def compress(l):
	l = list(set(l))
	l.sort()
	idx = defaultdict(int)
	for i in range(len(l)):
		idx[l[i]] = i
	return idx

def judge(x):
	l = []
	for ai in a:
		if ai >= x:
			l.append(1)
		else:
			l.append(-1)
	acc = [0] * (N + 1)
	for i in range(N):
		acc[i + 1] = acc[i] + l[i]
	idx = compress(acc)
	bit = BIT(len(idx.keys()))
	cnt = 0
	for i in range(N + 1):
		cnt += bit.acc(idx[acc[i]])
		bit.add(idx[acc[i]], 1)
	return cnt >= (N * (N + 1) // 2 + 1) // 2

def binary_search():
	(l, r) = (0, max(a))
	while l <= r:
		m = (l + r) // 2
		if judge(m):
			l = m + 1
		else:
			r = m - 1
	return r
N = int(input())
a = list(map(int, input().split()))
print(binary_search())


N = int(input())
A = list(map(int, input().split()))
A_sort = sorted(A)
ANSMIN = 0
ANSMAX = N - 1
cums = [None] * (N + 1)

def midup(x):
	cums[0] = 0
	for i in range(N):
		if A[i] >= x:
			cums[i + 1] = cums[i] + 1
		else:
			cums[i + 1] = cums[i] - 1
	MINS = min(cums)
	MAXS = max(cums)
	bitlist = [0 for i in range(MAXS - MINS + 2)]
	NUM = 0
	for i in range(N + 1):
		bitobje = cums[i] - MINS + 1
		x = bitobje
		while x != 0:
			NUM += bitlist[x]
			x -= x & -x
		while bitobje <= MAXS - MINS + 1:
			bitlist[bitobje] += 1
			bitobje += bitobje & -bitobje
	if NUM >= (N + 1) * N // 2 / 2:
		return 1
	else:
		return 0
while True:
	candi = A_sort[(ANSMIN + ANSMAX) // 2]
	if midup(candi) == 1:
		ANSMIN = (ANSMIN + ANSMAX) // 2
	else:
		ANSMAX = (ANSMIN + ANSMAX) // 2
	if A_sort[ANSMIN] == A_sort[ANSMAX]:
		print(A_sort[ANSMIN])
		break
	if ANSMIN + 1 == ANSMAX:
		if midup(A_sort[ANSMAX]) == 1:
			print(A_sort[ANSMAX])
			break
		else:
			print(A_sort[ANSMIN])
			break


import sys
input = sys.stdin.buffer.readline
from collections import defaultdict
con = 10 ** 9 + 7
INF = float('inf')

def getlist():
	return list(map(int, input().split()))

class BIT:

	def __init__(self, N):
		self.size = N
		self.tree = [0] * (N + 1)

	def sum(self, t):
		s = 0
		while t > 0:
			s += self.tree[t]
			t -= t & -t
		return s

	def add(self, t, x):
		while t <= self.size:
			self.tree[t] += x
			t += t & -t

def Binary_Search(A, B, N):
	left = 0
	right = N - 1
	ans = 0
	while left <= right:
		mid = (left + right) // 2
		var = B[mid]
		newlist = [None] * N
		for i in range(N):
			if A[i] >= var:
				newlist[i] = 1
			else:
				newlist[i] = -1
		newlistsum = [0]
		for i in range(N):
			newlistsum.append(newlistsum[-1] + newlist[i])
		cnt = 0
		bit = BIT(2 * N + 1)
		for i in range(N + 1):
			bit.add(newlistsum[i] + N, 1)
			cnt += bit.sum(newlistsum[i] + N) - 1
		if 4 * cnt >= N * (N + 1):
			ans = max(ans, B[mid])
			left = mid + 1
		else:
			right = mid - 1
	return ans

def main():
	N = int(input())
	A = getlist()
	B = sorted(A)
	ans = Binary_Search(A, B, N)
	print(ans)
main()


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
	S = [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)
	L = MAX - MIN + 1
	bit = [0] * (L + 1)
	ans = 0
	for S_i in S:
		S_i -= MIN - 1
		tmp = 0
		x = S_i
		while x > 0:
			tmp += bit[x]
			x -= x & -x
		ans += tmp
		x = S_i
		while x <= L:
			bit[x] += 1
			x += x & -x
	return ans
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)