#!/usr/bin/python

# -*- coding: utf-8 -*-

import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq



# decimal.getcontext().prec = 50

# sys.setrecursionlimit(10000)

# MOD = 10**9 + 7



def solve(f):

    n = f.read_int()

    a = f.read_int_list()



    if n == 1: return a[0]



    d = dict(list(zip(sorted(set(a)), list(range(len(a))))))



    def check(num):

        a1 = [0]*(n+1)

        a2 = [0]*(n+1)

        for i, ai in enumerate(a):

            if ai < num:

                a1[i+1] = a1[i]+1

                a2[i+1] = a2[i]

            else:

                a1[i+1] = a1[i]

                a2[i+1] = a2[i]+1

        ad = [a2[i]-a1[i]+10**5+1 for i in range(n+1)]



        bit = BinaryIndexedTree(2*10**5+1)

        cnt = 0

        for i in range(n+1):

            cnt += bit.sum(ad[i])

            bit.add(ad[i], 1)

        # print num, cnt



        return n*(n+1)/2 - cnt <= cnt



    mi = 0

    ma = 10**9+1



    while ma - mi > 1:

        mid = (ma+mi)/2

        if check(mid):

            mi = mid

        else:

            ma = mid



    return mi





class BinaryIndexedTree(object):

    """Binary Indexed Tree (1-indexed)"""

    def __init__(self, size, default=0):

        self.bit = [default for _ in range(size + 1)]

        self.size = size



    def sum(self, i):

        """sum 1 to i"""

        s = 0

        while i > 0:

            s += self.bit[i]

            i -= i & -i

        return s



    def add(self, i, x):

        """add x to bit[i]"""

        while i <= self.size:

            self.bit[i] += x

            i += i & -i





class Reader(object):

    def __init__(self, filename=None):

        self.file = open(filename) if filename is not None else None

        self.case = 1



    def __readline(self):

        return self.file.next().strip() if self.file else input()



    def next_case(self):

        next(self.file)

        self.case += 1



    def read_int(self): return int(self.__readline())

    def read_float(self): return float(self.__readline())

    def read_long(self): return int(self.__readline())

    def read_decimal(self): return decimal.Decimal(self.__readline())

    def read_str(self): return self.__readline()



    def read_int_list(self): return list(map(int, self.__readline().split()))

    def read_float_list(self): return list(map(float, self.__readline().split()))

    def read_long_list(self): return list(map(int, self.__readline().split()))

    def read_decimal_list(self): return list(map(decimal.Decimal, self.__readline().split()))

    def read_str_list(self): return self.__readline().split()



if __name__ == '__main__':

    filename = sys.argv[1] if len(sys.argv) > 1 else None

    f = Reader(filename)

    if f.file:

        while True:

            print("Case #%d\n"%f.case, solve(f))

            try:

                f.next_case()

            except StopIteration:

                break

    else:

        print(solve(f))

#!/usr/bin/python

# -*- coding: utf-8 -*-

import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq



# decimal.getcontext().prec = 50

# sys.setrecursionlimit(10000)

# MOD = 10**9 + 7



def solve(f):

    n = f.read_int()

    a = f.read_int_list()



    def check(num):

        aa = [10**5+1]*(n+1)

        for i, ai in enumerate(a):

            if ai < num:

                aa[i+1] = aa[i]-1

            else:

                aa[i+1] = aa[i]+1



        bit = BinaryIndexedTree(2*10**5+1)

        cnt = 0

        for i in range(n+1):

            cnt += bit.sum(aa[i])

            bit.add(aa[i], 1)



        return n*(n+1)/2 - cnt <= cnt



    mi = 0

    ma = 10**9+1



    while ma - mi > 1:

        mid = (ma+mi)/2

        if check(mid):

            mi = mid

        else:

            ma = mid



    return mi





class BinaryIndexedTree(object):

    """Binary Indexed Tree (1-indexed)"""

    def __init__(self, size, default=0):

        self.bit = [default for _ in range(size + 1)]

        self.size = size



    def sum(self, i):

        """sum 1 to i"""

        s = 0

        while i > 0:

            s += self.bit[i]

            i -= i & -i

        return s



    def add(self, i, x):

        """add x to bit[i]"""

        while i <= self.size:

            self.bit[i] += x

            i += i & -i





class Reader(object):

    def __init__(self, filename=None):

        self.file = open(filename) if filename is not None else None

        self.case = 1



    def __readline(self):

        return self.file.next().strip() if self.file else input()



    def next_case(self):

        next(self.file)

        self.case += 1



    def read_int(self): return int(self.__readline())

    def read_float(self): return float(self.__readline())

    def read_long(self): return int(self.__readline())

    def read_decimal(self): return decimal.Decimal(self.__readline())

    def read_str(self): return self.__readline()



    def read_int_list(self): return list(map(int, self.__readline().split()))

    def read_float_list(self): return list(map(float, self.__readline().split()))

    def read_long_list(self): return list(map(int, self.__readline().split()))

    def read_decimal_list(self): return list(map(decimal.Decimal, self.__readline().split()))

    def read_str_list(self): return self.__readline().split()



if __name__ == '__main__':

    filename = sys.argv[1] if len(sys.argv) > 1 else None

    f = Reader(filename)

    if f.file:

        while True:

            print("Case #%d\n"%f.case, solve(f))

            try:

                f.next_case()

            except StopIteration:

                break

    else:

        print(solve(f))

#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys, collections, itertools, re, math, fractions, decimal, random, array, bisect, heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7
def solve(f):
    n = f.read_int()
    a = f.read_int_list()
    if n == 1:
        return a[0]
    d = dict(list(zip(sorted(set(a)), list(range(len(a))))))

    def check(num):
        a1 = [0] * (n + 1)
        a2 = [0] * (n + 1)
        for i, ai in enumerate(a):
            if ai < num:
                a1[i + 1] = a1[i] + 1
                a2[i + 1] = a2[i]
            else:
                a1[i + 1] = a1[i]
                a2[i + 1] = a2[i] + 1
        ad = [a2[i] - a1[i] + 10**5 + 1 for i in range(n + 1)]
        bit = BinaryIndexedTree(2 * 10**5 + 1)
        cnt = 0
        for i in range(n + 1):
            cnt += bit.sum(ad[i])
            bit.add(ad[i], 1)
        # print num, cnt
        return n * (n + 1) / 2 - cnt <= cnt

    mi = 0
    ma = 10**9 + 1
    while ma - mi > 1:
        mid = (ma + mi) / 2
        if check(mid):
            mi = mid
        else:
            ma = mid
    return mi


class BinaryIndexedTree(object):
    """Binary Indexed Tree (1-indexed)"""

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

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

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


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else input()

    def next_case(self):
        next(self.file)
        self.case += 1

    def read_int(self):
        return int(self.__readline())

    def read_float(self):
        return float(self.__readline())

    def read_long(self):
        return int(self.__readline())

    def read_decimal(self):
        return decimal.Decimal(self.__readline())

    def read_str(self):
        return self.__readline()

    def read_int_list(self):
        return list(map(int, self.__readline().split()))

    def read_float_list(self):
        return list(map(float, self.__readline().split()))

    def read_long_list(self):
        return list(map(int, self.__readline().split()))

    def read_decimal_list(self):
        return list(map(decimal.Decimal, self.__readline().split()))

    def read_str_list(self):
        return self.__readline().split()


if __name__ == "__main__":
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print("Case #%d\n" % f.case, solve(f))
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print(solve(f))

#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys, collections, itertools, re, math, fractions, decimal, random, array, bisect, heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7
def solve(f):
    n = f.read_int()
    a = f.read_int_list()

    def check(num):
        aa = [10**5 + 1] * (n + 1)
        for i, ai in enumerate(a):
            if ai < num:
                aa[i + 1] = aa[i] - 1
            else:
                aa[i + 1] = aa[i] + 1
        bit = BinaryIndexedTree(2 * 10**5 + 1)
        cnt = 0
        for i in range(n + 1):
            cnt += bit.sum(aa[i])
            bit.add(aa[i], 1)
        return n * (n + 1) / 2 - cnt <= cnt

    mi = 0
    ma = 10**9 + 1
    while ma - mi > 1:
        mid = (ma + mi) / 2
        if check(mid):
            mi = mid
        else:
            ma = mid
    return mi


class BinaryIndexedTree(object):
    """Binary Indexed Tree (1-indexed)"""

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

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

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


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else input()

    def next_case(self):
        next(self.file)
        self.case += 1

    def read_int(self):
        return int(self.__readline())

    def read_float(self):
        return float(self.__readline())

    def read_long(self):
        return int(self.__readline())

    def read_decimal(self):
        return decimal.Decimal(self.__readline())

    def read_str(self):
        return self.__readline()

    def read_int_list(self):
        return list(map(int, self.__readline().split()))

    def read_float_list(self):
        return list(map(float, self.__readline().split()))

    def read_long_list(self):
        return list(map(int, self.__readline().split()))

    def read_decimal_list(self):
        return list(map(decimal.Decimal, self.__readline().split()))

    def read_str_list(self):
        return self.__readline().split()


if __name__ == "__main__":
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print("Case #%d\n" % f.case, solve(f))
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print(solve(f))

-    if n == 1: -        return a[0] -    d = dict(list(zip(sorted(set(a)), list(range(len(a)))))) -        a1 = [0] * (n + 1) -        a2 = [0] * (n + 1) +        aa = [10**5 + 1] * (n + 1) -                a1[i + 1] = a1[i] + 1 -                a2[i + 1] = a2[i] +                aa[i + 1] = aa[i] - 1 -                a1[i + 1] = a1[i] -                a2[i + 1] = a2[i] + 1 -        ad = [a2[i] - a1[i] + 10**5 + 1 for i in range(n + 1)] +                aa[i + 1] = aa[i] + 1 -            cnt += bit.sum(ad[i]) -            bit.add(ad[i], 1) -        # print num, cnt +            cnt += bit.sum(aa[i]) +            bit.add(aa[i], 1)