from itertools import accumulate

from math import ceil

 

N = int(eval(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)  # Binaryの先頭の分

lo, hi = -1, 10 ** 9 + 1

while hi - lo > 1:

    # Xは中央値候補

    X = (hi + lo) // 2

 

    # X以上なら1、X未満なら-1に変換

    Binary = [(1 if a >= X else -1) for a in A]

 

    # 累積和をとる

    Binary = list(accumulate(Binary))

 

    # BITを初期化

    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)
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(eval(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)  # Binaryの先頭の分
lo, hi = -1, 10**9 + 1
while hi - lo > 1:
    # Xは中央値候補
    X = (hi + lo) // 2
    # X以上なら1、X未満なら-1に変換
    Binary = [(1 if a >= X else -1) for a in A]
    # 累積和をとる
    Binary = list(accumulate(Binary))
    # BITを初期化
    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)

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 +import math -N = int(eval(input())) -A = list(map(int, input().split())) -if N == 1: -    print((A[0])) -    exit() +n = int(input()) +lst = list(map(int, input().split())) -class BinaryIndexedTree: +class Bit: -        self.bit = [0] * (n + 1) +        self.tree = [0] * (n + 1) -            s += self.bit[i] +            s += self.tree[i] -            self.bit[i] += x +            self.tree[i] += x -    def reset(self): -        self.bit = [0] * (self.size + 1) + +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 -BIT = BinaryIndexedTree(N)  # Binaryの先頭の分 -lo, hi = -1, 10**9 + 1 -while hi - lo > 1: -    # Xは中央値候補 -    X = (hi + lo) // 2 -    # X以上なら1、X未満なら-1に変換 -    Binary = [(1 if a >= X else -1) for a in A] -    # 累積和をとる -    Binary = list(accumulate(Binary)) -    # BITを初期化 -    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 +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 -        hi = X -print(lo) +        high = t +print(sorted_lst[high]) if judge(sorted_lst[high], lst, n) else print(sorted_lst[low])