Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

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

# 解説を参照
# https://img.atcoder.jp/arc101/editorial.pdf

def mergesort(S, f, t, T=None):
    """f <= i < j <= t かつ S[i] <= S[j] である(i,j)の個数.
       実行後, S[f:t]は整列済みになる."""
    if t - f <= 1:
        return 0

    # 作業スペース
    if T == None:
        T = [0] * len(S)

    mid = (f + t) // 2
    n1 = mergesort(S, f, mid, T)
    n2 = mergesort(S, mid, t, T)

    # マージ
    n = n1 + n2
    i = f
    j = mid
    k = f
    while i < mid:
        if j >= t or S[i] <= S[j]:
            T[k] = S[i]
            i += 1
            n += t - j
        else:
            T[k] = S[j]
            j += 1
        k += 1
    for i in range(f, k):
        S[i] = T[i]
    return n

def n_median_larger_than_or_equal_to(x):
    """aの部分列の中央値のうちx以上のものの個数"""

    # aの要素を -1, 1 に置換したリスト
    b = [-1 if e < x else 1 for e in a]

    # bの累積和
    S = [0]
    for e in b:
        S.append(S[-1] + e)

    # 和が0以上であるbの部分列の個数
    # == i < j and S[i] <= S[j] である(i,j)の個数
    return mergesort(S, 0, len(S))

# 条件を満たす x の最大値を2分探索で探す
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)


Fixed submission:
#!/usr/bin/env pypy3
# -*- coding: utf-8 -*-

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

# 解説を参照
# https://img.atcoder.jp/arc101/editorial.pdf

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):
    """リストSの転倒数"""
    global T
    T = [0] * len(S)
    return mergesort(S, 0, len(S))

def n_median_larger_than_or_equal_to(x):
    """aの部分列の中央値のうちx以上のものの個数"""

    # aの要素を -1, 1 に置換したリスト
    b = [-1 if e < x else 1 for e in a]
    # bの累積和
    S = [0]
    for e in b:
        S.append(S[-1] + e)
    # Sの転倒数
    return inversion(S)

# 条件を満たす x の最大値を2分探索で探す
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)

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

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

# 解説を参照
# https://img.atcoder.jp/arc101/editorial.pdf

def mergesort(S, f, t):
    if t - f <= 1:
        return 0, S[f:t]

    n1, S1 = mergesort(S, f, (f + t) // 2)
    n2, S2 = mergesort(S, (f + t) // 2, t)
    T = []
    n = 0
    i = 0
    j = 0
    while i < len(S1) and j < len(S2):
        if S1[i] <= S2[j]:
            T.append(S1[i])
            i += 1
            n += len(S2) - j
        else:
            T.append(S2[j])
            j += 1
    if i < len(S1):
        T.extend(S1[i:])
    if j < len(S2):
        T.extend(S2[j:])
    return n1 + n2 + n, T

def inversion(S):
    """リストSの転倒数"""
    n, __ = mergesort(S, 0, len(S))
    return n

def n_median_larger_than_or_equal_to(x):
    """aの部分列の中央値のうちx以上のものの個数"""

    # aの要素を -1, 1 に置換したリスト
    b = [-1 if e < x else 1 for e in a]
    # bの累積和
    S = [0]
    for e in b:
        S.append(S[-1] + e)
    # Sの転倒数
    return inversion(S)

# 条件を満たす x の最大値を2分探索で探す
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)


Fixed submission:
#!/usr/bin/env pypy3
# -*- coding: utf-8 -*-

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

# 解説を参照
# https://img.atcoder.jp/arc101/editorial.pdf

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):
    """リストSの転倒数"""
    global T
    T = [0] * len(S)
    return mergesort(S, 0, len(S))

def n_median_larger_than_or_equal_to(x):
    """aの部分列の中央値のうちx以上のものの個数"""

    # aの要素を -1, 1 に置換したリスト
    b = [-1 if e < x else 1 for e in a]
    # bの累積和
    S = [0]
    for e in b:
        S.append(S[-1] + e)
    # Sの転倒数
    return inversion(S)

# 条件を満たす x の最大値を2分探索で探す
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)