Buggy python submission (verdict: Time Limit Exceeded):
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:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0] * size
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        [0, i) の合計
        :param int 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

    # 中央値が k より小さくなる [l, r] の数
    # →[l, r] の総和がマイナスになる組み合わせの数
    # →転倒数
    bit = BinaryIndexedTree(size=max(cum) + 1)
    count = 0
    for i, c in enumerate(cum):
        count += i - bit.sum(c + 1)
        bit.add(c, 1)

        # 中央値が k より小さくなる数が半分より多ければ答えは k より小さい
        # NH2 = (N+1)C2
        if count > (N + 1) * N // 2 / 2:
            return True
    return False


def compress(li, origin=0):
    """
    座圧
    :param li:
    :param int origin:
    :rtype: list of int
    """
    *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):
    """
    累積和
    :param collections.Iterable it:
    :return:
    """
    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()))
# test(A)

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]])


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


class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0 for _ in range(size)]
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        0 番目から i 番目までの合計
        :param int i:
        :return:
        """
        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):
    """
    リストから転倒数 (li[i] > li[j] (i < j) となる (i, j) の組み合わせ数) を返す
    バブルソートするときに反転する必要がある数。
    :param numpy.ndarray | list of int li:
            すべての要素が 0 以上の int である配列。
            BIT を使うので、マイナスを含んだり最大値が大きい場合は np.argsort の結果を指定
            ただしリストに重複を含む場合は np.argsort は unstable なので別の方法使うこと
            https://docs.scipy.org/doc/numpy/reference/generated/numpy.sort.html
    :param int max: li の最大値。わかる場合は指定
    :rtype: int
    """
    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):
    """
    lo から hi-1 のうち、fn の結果が x 以上となる、最も左の値
    bisect.bisect_left と同じ
    https://docs.python.org/ja/3/library/bisect.html
    :param callable fn:
    :param x:
    :param int lo: 最小値
    :param int hi: 最大値 + 1
    :return: lo <= ret <= 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)

# L と r の選び方の組み合わせ数。1 から N までの和に等しい
lr_size = (N + 1) * N / 2


# cumsum[L] <= cumsum[r] となる (L, r) の組み合わせ数を数える
# 転倒数を数えて lr_size から引けばいい
# それが (lr_size + 1) // 2 以上である一番大きい x を探す
def solve(i):
    x = series_sorted[i]
    # series を x 以上かどうかで 1 と 0 に置換し累積和を取る
    cumsum_li = [0] + cumsum([1 if s >= x else -1 for s in series])
    # 転倒数 (cumsum にマイナスを含むので最小でも 0 になるよう N を加算）
    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))])

Buggy python submission (verdict: Time Limit Exceeded):
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:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0] * size
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        [0, i) の合計
        :param int 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)
    idx = argsort(cum)

    # 中央値が k より小さくなる [l, r] の数
    # →[l, r] の総和がマイナスになる組み合わせの数
    # →転倒数
    bit = BinaryIndexedTree(size=len(cum) + 1)
    count = 0
    while idx:
        n = cum[idx[-1]]
        li = []
        while idx and cum[idx[-1]] == n:
            li.append(idx.pop())
        for i in li:
            count += bit.sum(i)
        for i in li:
            bit.add(i, 1)

        # 中央値が k より小さくなる数が半分より多ければ答えは k より小さい
        # NH2 = (N+1)C2
        if count > (N + 1) * N // 2 / 2:
            return True
    return False


def compress(li, origin=0):
    """
    座圧
    :param li:
    :param int origin:
    :rtype: list of int
    """
    *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):
    """
    累積和
    :param collections.Iterable it:
    :return:
    """
    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()))
# test(A)

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]])


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


class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0 for _ in range(size)]
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        0 番目から i 番目までの合計
        :param int i:
        :return:
        """
        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):
    """
    リストから転倒数 (li[i] > li[j] (i < j) となる (i, j) の組み合わせ数) を返す
    バブルソートするときに反転する必要がある数。
    :param numpy.ndarray | list of int li:
            すべての要素が 0 以上の int である配列。
            BIT を使うので、マイナスを含んだり最大値が大きい場合は np.argsort の結果を指定
            ただしリストに重複を含む場合は np.argsort は unstable なので別の方法使うこと
            https://docs.scipy.org/doc/numpy/reference/generated/numpy.sort.html
    :param int max: li の最大値。わかる場合は指定
    :rtype: int
    """
    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):
    """
    lo から hi-1 のうち、fn の結果が x 以上となる、最も左の値
    bisect.bisect_left と同じ
    https://docs.python.org/ja/3/library/bisect.html
    :param callable fn:
    :param x:
    :param int lo: 最小値
    :param int hi: 最大値 + 1
    :return: lo <= ret <= 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)

# L と r の選び方の組み合わせ数。1 から N までの和に等しい
lr_size = (N + 1) * N / 2


# cumsum[L] <= cumsum[r] となる (L, r) の組み合わせ数を数える
# 転倒数を数えて lr_size から引けばいい
# それが (lr_size + 1) // 2 以上である一番大きい x を探す
def solve(i):
    x = series_sorted[i]
    # series を x 以上かどうかで 1 と 0 に置換し累積和を取る
    cumsum_li = [0] + cumsum([1 if s >= x else -1 for s in series])
    # 転倒数 (cumsum にマイナスを含むので最小でも 0 になるよう N を加算）
    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))])

Buggy python submission (verdict: Time Limit Exceeded):
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:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0] * size
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        [0, i) の合計
        :param int 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)
    idx = argsort(cum)

    # 中央値が k より小さくなる [l, r] の数
    # →[l, r] の総和がマイナスになる組み合わせの数
    # →転倒数
    bit = BinaryIndexedTree(size=len(cum) + 1)
    count = 0
    while idx:
        n = cum[idx[-1]]
        li = []
        while idx and cum[idx[-1]] == n:
            li.append(idx.pop())
        for i in li:
            count += bit.sum(i)
        for i in li:
            bit.add(i, 1)
    # 中央値が k より小さくなる数が半分より多ければ答えは k より小さい
    # NH2 = (N+1)C2
    return count > (N + 1) * N // 2 / 2


def compress(li, origin=0):
    """
    座圧
    :param li:
    :param int origin:
    :rtype: list of int
    """
    *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):
    """
    累積和
    :param collections.Iterable it:
    :return:
    """
    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()))
# test(A)

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]])


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


class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0 for _ in range(size)]
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        0 番目から i 番目までの合計
        :param int i:
        :return:
        """
        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):
    """
    リストから転倒数 (li[i] > li[j] (i < j) となる (i, j) の組み合わせ数) を返す
    バブルソートするときに反転する必要がある数。
    :param numpy.ndarray | list of int li:
            すべての要素が 0 以上の int である配列。
            BIT を使うので、マイナスを含んだり最大値が大きい場合は np.argsort の結果を指定
            ただしリストに重複を含む場合は np.argsort は unstable なので別の方法使うこと
            https://docs.scipy.org/doc/numpy/reference/generated/numpy.sort.html
    :param int max: li の最大値。わかる場合は指定
    :rtype: int
    """
    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):
    """
    lo から hi-1 のうち、fn の結果が x 以上となる、最も左の値
    bisect.bisect_left と同じ
    https://docs.python.org/ja/3/library/bisect.html
    :param callable fn:
    :param x:
    :param int lo: 最小値
    :param int hi: 最大値 + 1
    :return: lo <= ret <= 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)

# L と r の選び方の組み合わせ数。1 から N までの和に等しい
lr_size = (N + 1) * N / 2


# cumsum[L] <= cumsum[r] となる (L, r) の組み合わせ数を数える
# 転倒数を数えて lr_size から引けばいい
# それが (lr_size + 1) // 2 以上である一番大きい x を探す
def solve(i):
    x = series_sorted[i]
    # series を x 以上かどうかで 1 と 0 に置換し累積和を取る
    cumsum_li = [0] + cumsum([1 if s >= x else -1 for s in series])
    # 転倒数 (cumsum にマイナスを含むので最小でも 0 になるよう N を加算）
    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))])

Buggy python submission (verdict: Time Limit Exceeded):
import os
import sys

import numpy as np

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:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0] * size
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        [0, i) の合計
        :param int 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 = np.zeros(N + 1, dtype=int)
    arr[1:][B >= k] = 1
    arr[1:][B < k] = -1
    cum = arr.cumsum()
    idx = cum.argsort().tolist()
    cum = cum.tolist()

    # 中央値が k より小さくなる [l, r] の数
    # →[l, r] の総和がマイナスになる組み合わせの数
    # →転倒数
    bit = BinaryIndexedTree(size=len(cum) + 1)
    count = 0
    while idx:
        n = cum[idx[-1]]
        li = []
        while idx and cum[idx[-1]] == n:
            li.append(idx.pop())
        for i in li:
            count += bit.sum(i)
        for i in li:
            bit.add(i, 1)
    # 中央値が k より小さくなる数が半分より多ければ答えは k より小さい
    # NH2 = (N+1)C2
    return count > (N + 1) * N // 2 / 2


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))
A = np.array(A, dtype=int)
# test(A)

indices = A.argsort()

# 座圧
B = np.empty_like(A)
B[indices] = np.arange(N)

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]])


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


class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0 for _ in range(size)]
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        0 番目から i 番目までの合計
        :param int i:
        :return:
        """
        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):
    """
    リストから転倒数 (li[i] > li[j] (i < j) となる (i, j) の組み合わせ数) を返す
    バブルソートするときに反転する必要がある数。
    :param numpy.ndarray | list of int li:
            すべての要素が 0 以上の int である配列。
            BIT を使うので、マイナスを含んだり最大値が大きい場合は np.argsort の結果を指定
            ただしリストに重複を含む場合は np.argsort は unstable なので別の方法使うこと
            https://docs.scipy.org/doc/numpy/reference/generated/numpy.sort.html
    :param int max: li の最大値。わかる場合は指定
    :rtype: int
    """
    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):
    """
    lo から hi-1 のうち、fn の結果が x 以上となる、最も左の値
    bisect.bisect_left と同じ
    https://docs.python.org/ja/3/library/bisect.html
    :param callable fn:
    :param x:
    :param int lo: 最小値
    :param int hi: 最大値 + 1
    :return: lo <= ret <= 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)

# L と r の選び方の組み合わせ数。1 から N までの和に等しい
lr_size = (N + 1) * N / 2


# cumsum[L] <= cumsum[r] となる (L, r) の組み合わせ数を数える
# 転倒数を数えて lr_size から引けばいい
# それが (lr_size + 1) // 2 以上である一番大きい x を探す
def solve(i):
    x = series_sorted[i]
    # series を x 以上かどうかで 1 と 0 に置換し累積和を取る
    cumsum_li = [0] + cumsum([1 if s >= x else -1 for s in series])
    # 転倒数 (cumsum にマイナスを含むので最小でも 0 になるよう N を加算）
    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))])

Buggy python submission (verdict: Time Limit Exceeded):
def cumsum(li):
    ret = []
    sum = 0
    for i in li:
        sum += i
        ret.append(sum)
    return ret


class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0 for _ in range(size)]
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        0 番目から i 番目までの合計
        :param int i:
        :return:
        """
        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):
    """
    リストから転倒数 (li[i] > li[j] (i < j) となる (i, j) の組み合わせ数) を返す
    バブルソートするときに反転する必要がある数。
    :param numpy.ndarray | list of int li:
            すべての要素が 0 以上の int である配列。
            BIT を使うので、マイナスを含んだり最大値が大きい場合は np.argsort の結果を指定
            ただしリストに重複を含む場合は np.argsort は unstable なので別の方法使うこと
            https://docs.scipy.org/doc/numpy/reference/generated/numpy.sort.html
    :param int max: li の最大値。わかる場合は指定
    :rtype: int
    """
    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):
    """
    lo から hi-1 のうち、fn の結果が x 以上となる、最も左の値
    bisect.bisect_left と同じ
    https://docs.python.org/ja/3/library/bisect.html
    :param callable fn:
    :param x:
    :param int lo: 最小値
    :param int hi: 最大値 + 1
    :return: lo <= ret <= 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)

# L と r の選び方の組み合わせ数。1 から N までの和に等しい
lr_size = (N + 1) * N / 2


# cumsum[L] <= cumsum[r] となる (L, r) の組み合わせ数を数える
# 転倒数を数えて lr_size から引けばいい
# それが (lr_size + 1) // 2 以上である一番大きい x を探す
def solve(i):
    x = series_sorted[i]
    # series を x 以上かどうかで 1 と 0 に置換し累積和を取る
    cumsum_li = [0] + cumsum([1 if s >= x else -1 for s in series])
    # 転倒数 (cumsum にマイナスを含むので最小でも 0 になるよう N を加算）
    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))])


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


class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0 for _ in range(size)]
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        0 番目から i 番目までの合計
        :param int i:
        :return:
        """
        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):
    """
    リストから転倒数 (li[i] > li[j] (i < j) となる (i, j) の組み合わせ数) を返す
    バブルソートするときに反転する必要がある数。
    :param numpy.ndarray | list of int li:
            すべての要素が 0 以上の int である配列。
            BIT を使うので、マイナスを含んだり最大値が大きい場合は np.argsort の結果を指定
            ただしリストに重複を含む場合は np.argsort は unstable なので別の方法使うこと
            https://docs.scipy.org/doc/numpy/reference/generated/numpy.sort.html
    :param int max: li の最大値。わかる場合は指定
    :rtype: int
    """
    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):
    """
    lo から hi-1 のうち、fn の結果が x 以上となる、最も左の値
    bisect.bisect_left と同じ
    https://docs.python.org/ja/3/library/bisect.html
    :param callable fn:
    :param x:
    :param int lo: 最小値
    :param int hi: 最大値 + 1
    :return: lo <= ret <= 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)

# L と r の選び方の組み合わせ数。1 から N までの和に等しい
lr_size = (N + 1) * N / 2


# cumsum[L] <= cumsum[r] となる (L, r) の組み合わせ数を数える
# 転倒数を数えて lr_size から引けばいい
# それが (lr_size + 1) // 2 以上である一番大きい x を探す
def solve(i):
    x = series_sorted[i]
    # series を x 以上かどうかで 1 と 0 に置換し累積和を取る
    cumsum_li = [0] + cumsum([1 if s >= x else -1 for s in series])
    # 転倒数 (cumsum にマイナスを含むので最小でも 0 になるよう N を加算）
    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))])

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np


class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0 for _ in range(size)]
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        0 番目から i 番目までの合計
        :param int i:
        :return:
        """
        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):
    """
    リストから転倒数 (li[i] > li[j] (i < j) となる (i, j) の組み合わせ数) を返す
    バブルソートするときに反転する必要がある数。
    :param numpy.ndarray | list of int li:
            すべての要素が 0 以上の int である配列。
            BIT を使うので、マイナスを含んだり最大値が大きい場合は np.argsort の結果を指定
            ただしリストに重複を含む場合は np.argsort は unstable なので別の方法使うこと
            https://docs.scipy.org/doc/numpy/reference/generated/numpy.sort.html
    :param int max: li の最大値。わかる場合は指定
    :rtype: int
    """
    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):
    """
    lo から hi-1 のうち、fn の結果が x 以上となる、最も左の値
    bisect.bisect_left と同じ
    https://docs.python.org/ja/3/library/bisect.html
    :param callable fn:
    :param x:
    :param int lo: 最小値
    :param int hi: 最大値 + 1
    :return: lo <= ret <= hi
    """
    while lo < hi:
        mid = (lo + hi) // 2
        if fn(mid) < x:
            lo = mid + 1
        else:
            hi = mid
    return lo


N = int(input())
series = np.array(list(map(int, input().split())))

series_sorted = np.array(sorted(series))

# L と r の選び方の組み合わせ数。1 から N までの和に等しい
lr_size = (N + 1) * N / 2


# cumsum[L] <= cumsum[r] となる (L, r) の組み合わせ数を数える
# 転倒数を数えて lr_size から引けばいい
# それが (lr_size + 1) // 2 以上である一番大きい x を探す
def solve(i):
    x = series_sorted[i]
    # series を x 以上かどうかで 1 と 0 に置換し累積和を取る
    cumsum = np.array([0] + [1 if s >= x else -1 for s in series]).cumsum()
    # 転倒数 (cumsum にマイナスを含むので最小でも 0 になるよう N を加算）
    inversions = count_inversions(N + cumsum, 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))])


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


class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0 for _ in range(size)]
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        0 番目から i 番目までの合計
        :param int i:
        :return:
        """
        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):
    """
    リストから転倒数 (li[i] > li[j] (i < j) となる (i, j) の組み合わせ数) を返す
    バブルソートするときに反転する必要がある数。
    :param numpy.ndarray | list of int li:
            すべての要素が 0 以上の int である配列。
            BIT を使うので、マイナスを含んだり最大値が大きい場合は np.argsort の結果を指定
            ただしリストに重複を含む場合は np.argsort は unstable なので別の方法使うこと
            https://docs.scipy.org/doc/numpy/reference/generated/numpy.sort.html
    :param int max: li の最大値。わかる場合は指定
    :rtype: int
    """
    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):
    """
    lo から hi-1 のうち、fn の結果が x 以上となる、最も左の値
    bisect.bisect_left と同じ
    https://docs.python.org/ja/3/library/bisect.html
    :param callable fn:
    :param x:
    :param int lo: 最小値
    :param int hi: 最大値 + 1
    :return: lo <= ret <= 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)

# L と r の選び方の組み合わせ数。1 から N までの和に等しい
lr_size = (N + 1) * N / 2


# cumsum[L] <= cumsum[r] となる (L, r) の組み合わせ数を数える
# 転倒数を数えて lr_size から引けばいい
# それが (lr_size + 1) // 2 以上である一番大きい x を探す
def solve(i):
    x = series_sorted[i]
    # series を x 以上かどうかで 1 と 0 に置換し累積和を取る
    cumsum_li = [0] + cumsum([1 if s >= x else -1 for s in series])
    # 転倒数 (cumsum にマイナスを含むので最小でも 0 になるよう N を加算）
    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))])