Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate


class Bit:
    # 参考1: http://hos.ac/slides/20140319_bit.pdf
    # 参考2: https://atcoder.jp/contests/arc046/submissions/6264201
    # 検証: https://atcoder.jp/contests/arc046/submissions/7435621
    # values の 0 番目は使わない
    # len(values) を 2 冪 +1 にすることで二分探索の条件を減らす
    def __init__(self, a):
        if hasattr(a, "__iter__"):
            le = len(a)
            self.n = 1 << le.bit_length()  # le を超える最小の 2 冪
            self.values = values = [0] * (self.n + 1)
            values[1:le + 1] = a[:]
            for i in range(1, self.n):
                values[i + (i & -i)] += values[i]
        elif isinstance(a, int):
            self.n = 1 << a.bit_length()
            self.values = [0] * (self.n + 1)
        else:
            raise TypeError

    def add(self, i, val):
        n, values = self.n, self.values
        while i <= n:
            values[i] += val
            i += i & -i

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

    def bisect_left(self, v):  # self.sum(i) が v 以上になる最小の i
        n, values = self.n, self.values
        if v > values[n]:
            return None
        i, step = 0, n >> 1
        while step:
            if values[i + step] < v:
                i += step
                v -= values[i]
            step >>= 1
        return i + 1

def solve(M, N, A):
    A_sign = [-1 if a <= M else 1 for a in A]
    A_sign_cum = list(accumulate(A_sign))
    geta = N + 2
    bit = Bit(2*N + 4)
    bit.add(geta, 1)
    cnt = 0  # 中央値が M 以下になる区間の個数
    #if True:
    #    print(M, A_sign, A_sign_cum)
    for i, a in enumerate(A_sign_cum, 1):
        cnt += i - bit.sum(geta + a)
        #print(cnt, end=" ")
        bit.add(geta + a, 1)
    #print()
    #print(N * (N+1) // 4 + 1, cnt)
    return N * (N+1) // 4 + 1 <= cnt


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

    # cnt = 0
    # for i in range(N):
    #     for j in range(i+1, N+1):
    #         if sorted(A[i:j])[(j-i)//2] <= 5:
    #             cnt += 1
    #             print(i, j)
    # print(cnt)

    A_sorted = sorted(A)
    ng, ok = -1, N-1
    while ng + 1 < ok:
        c = (ng + ok) // 2
        M = A_sorted[c]
        if solve(M, N, A):
            ok = c
        else:
            ng = c
    print(A_sorted[ok])

main()


Fixed submission:
from itertools import accumulate


class Bit:
    # 参考1: http://hos.ac/slides/20140319_bit.pdf
    # 参考2: https://atcoder.jp/contests/arc046/submissions/6264201
    # 検証: https://atcoder.jp/contests/arc046/submissions/7435621
    # values の 0 番目は使わない
    # len(values) を 2 冪 +1 にすることで二分探索の条件を減らす
    def __init__(self, a):
        if hasattr(a, "__iter__"):
            le = len(a)
            self.n = 1 << le.bit_length()  # le を超える最小の 2 冪
            self.values = values = [0] * (self.n + 1)
            values[1:le + 1] = a[:]
            for i in range(1, self.n):
                values[i + (i & -i)] += values[i]
        elif isinstance(a, int):
            self.n = 1 << a.bit_length()
            self.values = [0] * (self.n + 1)
        else:
            raise TypeError

    def add(self, i, val):
        n, values = self.n, self.values
        while i <= n:
            values[i] += val
            i += i & -i

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

    def bisect_left(self, v):  # self.sum(i) が v 以上になる最小の i
        n, values = self.n, self.values
        if v > values[n]:
            return None
        i, step = 0, n >> 1
        while step:
            if values[i + step] < v:
                i += step
                v -= values[i]
            step >>= 1
        return i + 1

def solve(M, N, A):
    A_sign = [-1 if a <= M else 1 for a in A]
    A_sign_cum = list(accumulate(A_sign))
    geta = N + 2
    bit = Bit(2*N + 4)
    bit.add(geta, 1)
    cnt = 0  # 中央値が M 以下になる区間の個数
    #if True:
    #    print(M, A_sign, A_sign_cum)
    for i, a in enumerate(A_sign_cum, 1):
        cnt += i - bit.sum(geta + a)
        #print(cnt, end=" ")
        bit.add(geta + a, 1)
    #print()
    #print(N * (N+1) // 4 + 1, cnt)
    return N * (N+1) // 4 + 1 <= cnt


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

    # cnt = 0
    # for i in range(N):
    #     for j in range(i+1, N+1):
    #         if sorted(A[i:j])[(j-i)//2] <= 5:
    #             cnt += 1
    #             print(i, j)
    # print(cnt)

    A_sorted = sorted(A)
    ng, ok = -1, N-1
    while ng + 1 < ok:
        c = (ng + ok) // 2
        M = A_sorted[c]
        if solve(M, N, A):
            ok = c
        else:
            ng = c
    print(A_sorted[ok])

main()

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate

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

    def __iter__(self):
        psum = 0
        for i in range(self.size):
            csum = self.sum(i+1)
            yield csum - psum
            psum = csum
        raise StopIteration()

    def __str__(self):  # O(nlogn)
        return str(list(self))

    def sum(self, i):
        # [0, i) の要素の総和を返す
        #if not (0 <= i <= self.size): raise ValueError("error!")
        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 __getitem__(self, key):
        #if not (0 <= key < self.size): raise IndexError("error!")
        return self.sum(key+1) - self.sum(key)

    def __setitem__(self, key, value):
        # 足し算と引き算にはaddを使うべき
        if not (0 <= key < self.size): raise IndexError("error!")
        self.add(key, value - self[key])


def solve(M, N, A):
    A_sign = [-1 if a <= M else 1 for a in A]
    A_sign_cum = list(accumulate(A_sign))
    geta = N + 2
    bit = Bit(2*N + 4)
    bit.add(geta, 1)
    cnt = 0  # 中央値が M 以下になる区間の個数
    #if True:
    #    print(M, A_sign, A_sign_cum)
    for i, a in enumerate(A_sign_cum, 1):
        cnt += i - bit.sum(geta + a + 1)
        #print(cnt, end=" ")
        bit.add(geta + a, 1)
    #print()
    #print(N * (N+1) // 4 + 1, cnt)
    return N * (N+1) // 4 + 1 <= cnt


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

    # cnt = 0
    # for i in range(N):
    #     for j in range(i+1, N+1):
    #         if sorted(A[i:j])[(j-i)//2] <= 5:
    #             cnt += 1
    #             print(i, j)
    # print(cnt)

    A_sorted = sorted(A)
    ng, ok = -1, N-1
    while ng + 1 < ok:
        c = (ng + ok) // 2
        M = A_sorted[c]
        if solve(M, N, A):
            ok = c
        else:
            ng = c
    print(A_sorted[ok])

main()


Fixed submission:
from itertools import accumulate


class Bit:
    # 参考1: http://hos.ac/slides/20140319_bit.pdf
    # 参考2: https://atcoder.jp/contests/arc046/submissions/6264201
    # 検証: https://atcoder.jp/contests/arc046/submissions/7435621
    # values の 0 番目は使わない
    # len(values) を 2 冪 +1 にすることで二分探索の条件を減らす
    def __init__(self, a):
        if hasattr(a, "__iter__"):
            le = len(a)
            self.n = 1 << le.bit_length()  # le を超える最小の 2 冪
            self.values = values = [0] * (self.n + 1)
            values[1:le + 1] = a[:]
            for i in range(1, self.n):
                values[i + (i & -i)] += values[i]
        elif isinstance(a, int):
            self.n = 1 << a.bit_length()
            self.values = [0] * (self.n + 1)
        else:
            raise TypeError

    def add(self, i, val):
        n, values = self.n, self.values
        while i <= n:
            values[i] += val
            i += i & -i

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

    def bisect_left(self, v):  # self.sum(i) が v 以上になる最小の i
        n, values = self.n, self.values
        if v > values[n]:
            return None
        i, step = 0, n >> 1
        while step:
            if values[i + step] < v:
                i += step
                v -= values[i]
            step >>= 1
        return i + 1

def solve(M, N, A):
    A_sign = [-1 if a <= M else 1 for a in A]
    A_sign_cum = list(accumulate(A_sign))
    geta = N + 2
    bit = Bit(2*N + 4)
    bit.add(geta, 1)
    cnt = 0  # 中央値が M 以下になる区間の個数
    #if True:
    #    print(M, A_sign, A_sign_cum)
    for i, a in enumerate(A_sign_cum, 1):
        cnt += i - bit.sum(geta + a)
        #print(cnt, end=" ")
        bit.add(geta + a, 1)
    #print()
    #print(N * (N+1) // 4 + 1, cnt)
    return N * (N+1) // 4 + 1 <= cnt


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

    # cnt = 0
    # for i in range(N):
    #     for j in range(i+1, N+1):
    #         if sorted(A[i:j])[(j-i)//2] <= 5:
    #             cnt += 1
    #             print(i, j)
    # print(cnt)

    A_sorted = sorted(A)
    ng, ok = -1, N-1
    while ng + 1 < ok:
        c = (ng + ok) // 2
        M = A_sorted[c]
        if solve(M, N, A):
            ok = c
        else:
            ng = c
    print(A_sorted[ok])

main()

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate

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

    def __iter__(self):
        psum = 0
        for i in range(self.size):
            csum = self.sum(i+1)
            yield csum - psum
            psum = csum
        raise StopIteration()

    def __str__(self):  # O(nlogn)
        return str(list(self))

    def sum(self, i):
        # [0, i) の要素の総和を返す
        #if not (0 <= i <= self.size): raise ValueError("error!")
        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 __getitem__(self, key):
        #if not (0 <= key < self.size): raise IndexError("error!")
        return self.sum(key+1) - self.sum(key)

    def __setitem__(self, key, value):
        # 足し算と引き算にはaddを使うべき
        if not (0 <= key < self.size): raise IndexError("error!")
        self.add(key, value - self[key])


def solve(M):
    A_sign = [-1 if a <= M else 1 for a in A]
    A_sign_cum = list(accumulate(A_sign))
    geta = N + 2
    bit = Bit(2*N + 4)
    bit.add(geta, 1)
    cnt = 0  # 中央値が M 以下になる区間の個数
    #if True:
    #    print(M, A_sign, A_sign_cum)
    for i, a in enumerate(A_sign_cum, 1):
        cnt += i - bit.sum(geta + a + 1)
        #print(cnt, end=" ")
        bit.add(geta + a, 1)
    #print()
    #print(N * (N+1) // 4 + 1, cnt)
    return N * (N+1) // 4 + 1 <= cnt


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

# cnt = 0
# for i in range(N):
#     for j in range(i+1, N+1):
#         if sorted(A[i:j])[(j-i)//2] <= 5:
#             cnt += 1
#             print(i, j)
# print(cnt)

A_sorted = sorted(A)
ng, ok = -1, N-1
while ng + 1 < ok:
    c = (ng + ok) // 2
    M = A_sorted[c]
    if solve(M):
        ok = c
    else:
        ng = c
print(A_sorted[ok])


Fixed submission:
from itertools import accumulate


class Bit:
    # 参考1: http://hos.ac/slides/20140319_bit.pdf
    # 参考2: https://atcoder.jp/contests/arc046/submissions/6264201
    # 検証: https://atcoder.jp/contests/arc046/submissions/7435621
    # values の 0 番目は使わない
    # len(values) を 2 冪 +1 にすることで二分探索の条件を減らす
    def __init__(self, a):
        if hasattr(a, "__iter__"):
            le = len(a)
            self.n = 1 << le.bit_length()  # le を超える最小の 2 冪
            self.values = values = [0] * (self.n + 1)
            values[1:le + 1] = a[:]
            for i in range(1, self.n):
                values[i + (i & -i)] += values[i]
        elif isinstance(a, int):
            self.n = 1 << a.bit_length()
            self.values = [0] * (self.n + 1)
        else:
            raise TypeError

    def add(self, i, val):
        n, values = self.n, self.values
        while i <= n:
            values[i] += val
            i += i & -i

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

    def bisect_left(self, v):  # self.sum(i) が v 以上になる最小の i
        n, values = self.n, self.values
        if v > values[n]:
            return None
        i, step = 0, n >> 1
        while step:
            if values[i + step] < v:
                i += step
                v -= values[i]
            step >>= 1
        return i + 1

def solve(M, N, A):
    A_sign = [-1 if a <= M else 1 for a in A]
    A_sign_cum = list(accumulate(A_sign))
    geta = N + 2
    bit = Bit(2*N + 4)
    bit.add(geta, 1)
    cnt = 0  # 中央値が M 以下になる区間の個数
    #if True:
    #    print(M, A_sign, A_sign_cum)
    for i, a in enumerate(A_sign_cum, 1):
        cnt += i - bit.sum(geta + a)
        #print(cnt, end=" ")
        bit.add(geta + a, 1)
    #print()
    #print(N * (N+1) // 4 + 1, cnt)
    return N * (N+1) // 4 + 1 <= cnt


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

    # cnt = 0
    # for i in range(N):
    #     for j in range(i+1, N+1):
    #         if sorted(A[i:j])[(j-i)//2] <= 5:
    #             cnt += 1
    #             print(i, j)
    # print(cnt)

    A_sorted = sorted(A)
    ng, ok = -1, N-1
    while ng + 1 < ok:
        c = (ng + ok) // 2
        M = A_sorted[c]
        if solve(M, N, A):
            ok = c
        else:
            ng = c
    print(A_sorted[ok])

main()

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate

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

    def __iter__(self):
        psum = 0
        for i in range(self.size):
            csum = self.sum(i+1)
            yield csum - psum
            psum = csum
        raise StopIteration()

    def __str__(self):  # O(nlogn)
        return str(list(self))

    def sum(self, i):
        # [0, i) の要素の総和を返す
        if not (0 <= i <= self.size): raise ValueError("error!")
        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 __getitem__(self, key):
        if not (0 <= key < self.size): raise IndexError("error!")
        return self.sum(key+1) - self.sum(key)

    def __setitem__(self, key, value):
        # 足し算と引き算にはaddを使うべき
        if not (0 <= key < self.size): raise IndexError("error!")
        self.add(key, value - self[key])


def solve(M):
    A_sign = [-1 if a <= M else 1 for a in A]
    A_sign_cum = list(accumulate(A_sign))
    geta = 2 * N
    bit = Bit(4*N)
    bit.add(geta, 1)
    cnt = 0  # 中央値が M 以下になる区間の個数
    #if True:
    #    print(M, A_sign, A_sign_cum)
    for i, a in enumerate(A_sign_cum, 1):
        cnt += i - bit.sum(geta + a + 1)
        #print(cnt, end=" ")
        bit.add(geta + a, 1)
    #print()
    #print(N * (N+1) // 4 + 1, cnt)
    return N * (N+1) // 4 + 1 <= cnt


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

# cnt = 0
# for i in range(N):
#     for j in range(i+1, N+1):
#         if sorted(A[i:j])[(j-i)//2] <= 5:
#             cnt += 1
#             print(i, j)
# print(cnt)

A_sorted = sorted(A)
ng, ok = -1, N-1
while ng + 1 < ok:
    c = (ng + ok) // 2
    M = A_sorted[c]
    if solve(M):
        ok = c
    else:
        ng = c
print(A_sorted[ok])


Fixed submission:
from itertools import accumulate


class Bit:
    # 参考1: http://hos.ac/slides/20140319_bit.pdf
    # 参考2: https://atcoder.jp/contests/arc046/submissions/6264201
    # 検証: https://atcoder.jp/contests/arc046/submissions/7435621
    # values の 0 番目は使わない
    # len(values) を 2 冪 +1 にすることで二分探索の条件を減らす
    def __init__(self, a):
        if hasattr(a, "__iter__"):
            le = len(a)
            self.n = 1 << le.bit_length()  # le を超える最小の 2 冪
            self.values = values = [0] * (self.n + 1)
            values[1:le + 1] = a[:]
            for i in range(1, self.n):
                values[i + (i & -i)] += values[i]
        elif isinstance(a, int):
            self.n = 1 << a.bit_length()
            self.values = [0] * (self.n + 1)
        else:
            raise TypeError

    def add(self, i, val):
        n, values = self.n, self.values
        while i <= n:
            values[i] += val
            i += i & -i

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

    def bisect_left(self, v):  # self.sum(i) が v 以上になる最小の i
        n, values = self.n, self.values
        if v > values[n]:
            return None
        i, step = 0, n >> 1
        while step:
            if values[i + step] < v:
                i += step
                v -= values[i]
            step >>= 1
        return i + 1

def solve(M, N, A):
    A_sign = [-1 if a <= M else 1 for a in A]
    A_sign_cum = list(accumulate(A_sign))
    geta = N + 2
    bit = Bit(2*N + 4)
    bit.add(geta, 1)
    cnt = 0  # 中央値が M 以下になる区間の個数
    #if True:
    #    print(M, A_sign, A_sign_cum)
    for i, a in enumerate(A_sign_cum, 1):
        cnt += i - bit.sum(geta + a)
        #print(cnt, end=" ")
        bit.add(geta + a, 1)
    #print()
    #print(N * (N+1) // 4 + 1, cnt)
    return N * (N+1) // 4 + 1 <= cnt


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

    # cnt = 0
    # for i in range(N):
    #     for j in range(i+1, N+1):
    #         if sorted(A[i:j])[(j-i)//2] <= 5:
    #             cnt += 1
    #             print(i, j)
    # print(cnt)

    A_sorted = sorted(A)
    ng, ok = -1, N-1
    while ng + 1 < ok:
        c = (ng + ok) // 2
        M = A_sorted[c]
        if solve(M, N, A):
            ok = c
        else:
            ng = c
    print(A_sorted[ok])

main()