Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


class BinaryIndexTree:
    def __init__(self, n):
        self._size = n
        self._tree = [0] * (n+1)

    def sum(self, i):
        s = 0
        i += 1
        while 0 < i:
            s += self._tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        i += 1
        while i <= self._size:
            self._tree[i-1] += x
            i += i & -i


def solve(N: int, a: "List[int]"):
    c = N * (N + 1) // 2
    th = (c + 1) // 2

    xs = list(sorted(set(a)))
    lo = 0
    hi = len(xs)

    def _f(x):
        ss = [0] + list(accumulate([1 if x <= v else -1 for v in a]))
        n = max([abs(s) for s in ss])
        bit = BinaryIndexTree(2 * n + 1)

        ret = 0
        for s in ss:
            ret += bit.sum(s + n) 
            bit.add(s + n, 1)
        return ret

    while (lo + 1) < hi:
        mid = (lo + hi) // 2
        if th <= _f(xs[mid]):
            lo = mid
        else:
            hi = mid
    return xs[lo]


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    result = solve(N, a)
    print(result)

if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


class BinaryIndexTree:
    def __init__(self, n):
        self._size = n
        self._tree = [0] * (n+1)

    def sum(self, i):
        s = 0
        i += 1
        while 0 < i:
            s += self._tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        i += 1
        while i <= self._size:
            self._tree[i-1] += x
            i += i & -i


def solve(N: int, a: "List[int]"):
    c = N * (N + 1) // 2
    th = (c + 1) // 2

    xs = list(sorted(set(a)))
    lo = 0
    hi = len(xs)

    def _f(x):
        ss = [0] + list(accumulate([1 if x <= v else -1 for v in a]))
        n = max([abs(s) for s in ss])
        bit = BinaryIndexTree(2 * n + 1)

        ret = 0
        for s in ss:
            ret += bit.sum(s + n) 
            bit.add(s + n, 1)
        return ret

    while (lo + 1) < hi:
        mid = (lo + hi) // 2
        if th <= _f(xs[mid]):
            lo = mid
        else:
            hi = mid
    return xs[lo]


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    result = solve(N, a)
    print(result)

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


class BinaryIndexTree:
    def __init__(self, n):
        self._size = n
        self._tree = [0] * (n+1)

    def sum(self, i):
        s = 0
        i += 1
        while 0 < i:
            s += self._tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        i += 1
        while i <= self._size:
            self._tree[i-1] += x
            i += i & -i


def solve(N: int, a: "List[int]"):
    c = N * (N + 1) // 2
    th = (c + 1 ) // 2

    xs = list(sorted(set(a)))
    lo = 0
    hi = len(xs)

    def _f(x):
        ss = [0] + list(accumulate([1 if x <= v else -1 for v in a]))
        n = max([abs(s) for s in ss])
        bit = BinaryIndexTree(2 * n + 1)

        ret = 0
        for s in ss:
            bit.add(s + n, 1)
            ret += bit.sum(s + n - 1)
        return ret

    while lo < hi:
        mid = (lo + hi) // 2
        if th < _f(xs[mid]):
            lo = mid + 1
        else:
            hi = mid
    return xs[lo]


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    result = solve(N, a)
    print(result)

if __name__ == '__main__':
    main()

Fixed submission:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


class BinaryIndexTree:
    def __init__(self, n):
        self._size = n
        self._tree = [0] * (n+1)

    def sum(self, i):
        s = 0
        i += 1
        while 0 < i:
            s += self._tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        i += 1
        while i <= self._size:
            self._tree[i-1] += x
            i += i & -i


def solve(N: int, a: "List[int]"):
    c = N * (N + 1) // 2
    th = (c + 1) // 2

    xs = list(sorted(set(a)))
    lo = 0
    hi = len(xs)

    def _f(x):
        ss = [0] + list(accumulate([1 if x <= v else -1 for v in a]))
        n = max([abs(s) for s in ss])
        bit = BinaryIndexTree(2 * n + 1)

        ret = 0
        for s in ss:
            ret += bit.sum(s + n) 
            bit.add(s + n, 1)
        return ret

    while (lo + 1) < hi:
        mid = (lo + hi) // 2
        if th <= _f(xs[mid]):
            lo = mid
        else:
            hi = mid
    return xs[lo]


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    result = solve(N, a)
    print(result)

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


class BinaryIndexTree:
    def __init__(self, n):
        self._size = n
        self._tree = [0] * (n+1)

    def sum(self, i):
        s = 0
        i += 1
        while 0 < i:
            s += self._tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        i += 1
        while i <= self._size:
            self._tree[i-1] += x
            i += i & -i

# 転倒数の取得
def get_inv(A):
    N=len(A)
    # マイナスの値を考慮するため今回は*2する
    bit=BIT(N*2+1)
    ans=0
    for i in range(N-1, -1, -1):
        bit.add(A[i]+N, 1)
        # 自分より右にある、自分より小さな数の個数
        ans+=bit.sum(A[i]+N-1)
    return ans

def calc(X):
    # X以上かどうかで1と-1にする配列L
    L=[0]*N
    for i in range(N):
        if A[i]>=X:
            L[i]=1
        else:
            L[i]=-1
    # 累積和
    sm=[0]+list(accumulate(L))
    # 区間の全組み合わせ - 累積和の転倒数(1より-1のが多かった区間の数)
    # = 中央値がX以上となる区間の数(1のが多いor同数だった区間の数)
    ans=ALL-get_inv(sm)
    # 中央値がX以上となる区間が、全体の半分(切り上げ)以上あるかどうか
    return ans>=ceil(ALL, 2)



def solve(N: int, a: "List[int]"):
    th = N * (N + 1) // 4

    xs = list(sorted(set(a)))
    lo = 0
    hi = len(xs) - 1


    def _f(x):
        ss = [0] + list(accumulate([1 if x <= v else -1 for v in a]))
        n = max([abs(s) for s in ss])
        bit = BinaryIndexTree(2 * n + 1)

        ret = 0
        for s in ss:
            bit.add(s + n, 1)
            ret += bit.sum(s + n - 1) 

        return ret

    while lo < hi:
        mid = (lo + hi) // 2
        if th < _f(xs[mid]):
            lo = mid + 1
        else:
            hi = mid
    return xs[lo]


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    result = solve(N, a)
    print(result)

if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


class BinaryIndexTree:
    def __init__(self, n):
        self._size = n
        self._tree = [0] * (n+1)

    def sum(self, i):
        s = 0
        i += 1
        while 0 < i:
            s += self._tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        i += 1
        while i <= self._size:
            self._tree[i-1] += x
            i += i & -i


def solve(N: int, a: "List[int]"):
    c = N * (N + 1) // 2
    th = (c + 1) // 2

    xs = list(sorted(set(a)))
    lo = 0
    hi = len(xs)

    def _f(x):
        ss = [0] + list(accumulate([1 if x <= v else -1 for v in a]))
        n = max([abs(s) for s in ss])
        bit = BinaryIndexTree(2 * n + 1)

        ret = 0
        for s in ss:
            ret += bit.sum(s + n) 
            bit.add(s + n, 1)
        return ret

    while (lo + 1) < hi:
        mid = (lo + hi) // 2
        if th <= _f(xs[mid]):
            lo = mid
        else:
            hi = mid
    return xs[lo]


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    result = solve(N, a)
    print(result)

if __name__ == '__main__':
    main()