Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
x = list(sorted(set(a)))
n_sub = n * (n + 1) // 2
Li = -1
Ri = len(x) - 1
while Ri > Li + 1:
    i = (Li + Ri) // 2
    xi = x[i]
    UorD = [1 if ak >= xi else -1 for ak in a]
    cnt_sum = [0] * (2 * n + 1)
    cumsum = 0
    cnt_sum[cumsum + n] = 1
    tmp = 0
    for uk in UorD:
        cumsum += uk
        cnt_sum[cumsum + n] += 1
        tmp += sum(cnt_sum[:cumsum + n])
        if tmp >= n_sub // 2:
            Li = i
            break
    else:
        Ri = i
print(x[Ri])


Fixed submission:
n = int(input())
a = list(map(int, input().split()))
x = list(sorted(set(a)))
n_sub = n * (n + 1) // 2
Li = 0
Ri = len(x)
while Ri > Li + 1:
    i = (Li + Ri) // 2
    xi = x[i]
    UorD = [1 if ak >= xi else -1 for ak in a]
    cnt_sum = [0] * (2 * n + 1)
    cumsum = 0
    cnt_sum[cumsum + n] = 1
    judge = 0
    s = 0
    for uk in UorD:
        cumsum += uk
        if uk == 1:
            s += cnt_sum[cumsum + n] + 1
        else:
            s -= cnt_sum[cumsum + n + 1] - 1
        cnt_sum[cumsum + n] += 1
        judge += s
        if judge >= n_sub // 2:
            Li = i
            break
    else:
        Ri = i
print(x[Li])

Buggy python submission (verdict: Time Limit Exceeded):
# 1のnumpyバージョン
import numpy as np
def f():
    n = int(input())
    a = list(map(int, input().split()))
    x = list(sorted(set(a)))
    a = np.array(a, dtype="i8")
    Li = -1
    Ri = len(x) - 1
    while Li + 1 < Ri:
        i = (Li + Ri) // 2
        xi = x[i]
        s = 0
        lr = np.cumsum((a > xi) * 2 - 1, dtype="i8")
        M = np.sum((lr >= 0) * 2 - 1)
        for l in range(1, n):
            lr[l:] -= lr[l - 1]
            M += np.sum((lr[l:] >= 0) * 2 - 1)
        if M >= 0:
            Li = i
        else:
            Ri = i
    print(x[Ri])

f()

Fixed submission:
n = int(input())
a = list(map(int, input().split()))
x = list(sorted(set(a)))
n_sub = n * (n + 1) // 2
Li = 0
Ri = len(x)
while Ri > Li + 1:
    i = (Li + Ri) // 2
    xi = x[i]
    UorD = [1 if ak >= xi else -1 for ak in a]
    cnt_sum = [0] * (2 * n + 1)
    cumsum = 0
    cnt_sum[cumsum + n] = 1
    judge = 0
    s = 0
    for uk in UorD:
        cumsum += uk
        if uk == 1:
            s += cnt_sum[cumsum + n] + 1
        else:
            s -= cnt_sum[cumsum + n + 1] - 1
        cnt_sum[cumsum + n] += 1
        judge += s
        if judge >= n_sub // 2:
            Li = i
            break
    else:
        Ri = i
print(x[Li])

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

n = int(input())
a = list(map(int, input().split()))
x = list(sorted(set(a)))
a = np.array(a, dtype="i8")
Li = -1
Ri = len(x) - 1
while Li + 1 < Ri:
    i = (Li + Ri) // 2
    xi = x[i]
    s = 0
    lr = np.cumsum((a > xi) * 2 - 1, dtype="i8")
    M = np.sum((lr >= 0) * 2 - 1)
    for l in range(1, n):
        lr[l:] -= lr[l - 1]
        M += np.sum((lr[l:] >= 0) * 2 - 1)
    if M >= 0:
        Li = i
    else:
        Ri = i
print(x[Ri])


Fixed submission:
n = int(input())
a = list(map(int, input().split()))
x = list(sorted(set(a)))
n_sub = n * (n + 1) // 2
Li = 0
Ri = len(x)
while Ri > Li + 1:
    i = (Li + Ri) // 2
    xi = x[i]
    UorD = [1 if ak >= xi else -1 for ak in a]
    cnt_sum = [0] * (2 * n + 1)
    cumsum = 0
    cnt_sum[cumsum + n] = 1
    judge = 0
    s = 0
    for uk in UorD:
        cumsum += uk
        if uk == 1:
            s += cnt_sum[cumsum + n] + 1
        else:
            s -= cnt_sum[cumsum + n + 1] - 1
        cnt_sum[cumsum + n] += 1
        judge += s
        if judge >= n_sub // 2:
            Li = i
            break
    else:
        Ri = i
print(x[Li])

Buggy python submission (verdict: Time Limit Exceeded):
def update(i, x):
    while i < n:
        bit[i] += x
        i += i & -i


def getsum(i):
    s = 0
    while i:
        s += bit[i]
        i -= i & -i
    return s


def f(n, a, x):
    Li = -1
    Ri = len(x) - 1
    i = (Li + Ri) // 2
    xi = x[i]
    for ai, ak in enumerate(a):
        update(ai + 1, (ak > xi) * 2 - 1)
    lr = [0] * n

    while 1:
        M = 0
        for r in range(n):
            lr[r] = tmp = getsum(r + 1)
            M += (tmp >= 0) * 2 - 1
        for l in range(1, n):
            for r in range(l, n):
                lr[r] = tmp = lr[r] - lr[l - 1]
                M += (tmp >= 0) * 2 - 1
        if M >= 0:
            Li = i
        else:
            Ri = i
        if Li + 1 == Ri: break
        pi = i
        i = (Li + Ri) // 2
        if i < pi:
            s = x[i + 1]
            b = x[pi]
            dt = 2
        else:
            s = x[pi + 1]
            b = x[i]
            dt = -2
        for ai, ak in enumerate(a):
            if s <= ak <= b:
                update(ai + 1, dt)
    print(x[Ri])


n = int(input())
a = list(map(int, input().split()))
x = list(sorted(set(a)))
bit = [0] * (n + 1)
f(n, a, x)


Fixed submission:
n = int(input())
a = list(map(int, input().split()))
x = list(sorted(set(a)))
n_sub = n * (n + 1) // 2
Li = 0
Ri = len(x)
while Ri > Li + 1:
    i = (Li + Ri) // 2
    xi = x[i]
    UorD = [1 if ak >= xi else -1 for ak in a]
    cnt_sum = [0] * (2 * n + 1)
    cumsum = 0
    cnt_sum[cumsum + n] = 1
    judge = 0
    s = 0
    for uk in UorD:
        cumsum += uk
        if uk == 1:
            s += cnt_sum[cumsum + n] + 1
        else:
            s -= cnt_sum[cumsum + n + 1] - 1
        cnt_sum[cumsum + n] += 1
        judge += s
        if judge >= n_sub // 2:
            Li = i
            break
    else:
        Ri = i
print(x[Li])

Buggy python submission (verdict: Time Limit Exceeded):
def update(i, x):
    while i < n:
        bit[i] += x
        i += i & -i


def getsum(i):
    s = 0
    while i:
        s += bit[i]
        i -= i & -i
    return s


def f(n, a, x):
    Li = -1
    Ri = len(x) - 1
    i = (Li + Ri) // 2
    xi = x[i]
    for ai, ak in enumerate(a):
        update(ai + 1, (ak > xi) * 2 - 1)
    lr = [0] * n

    while 1:
        M = 0
        for r in range(n):
            lr[r] = tmp = getsum(r + 1)
            M += (tmp >= 0) * 2 - 1
        for l in range(1, n):
            for r in range(l, n):
                lr[r] = tmp = lr[r] - lr[l - 1]
                M += (tmp >= 0) * 2 - 1
        if M >= 0:
            Li = i
        else:
            Ri = i
        if Li + 1 == Ri: break
        pi = i
        i = (Li + Ri) // 2
        if i < pi:
            s = x[i + 1]
            b = x[pi]
            dt = 2
        else:
            s = x[pi + 1]
            b = x[i]
            dt = -2
        for ai, ak in enumerate(a):
            if s <= ak <= b:
                update(ai + 1, dt)
    print(x[Ri])


n = int(input())
a = list(map(int, input().split()))
x = list(sorted(set(a)))
bit = [0] * (n + 1)
f(n, a, x)


Fixed submission:
n = int(input())
a = list(map(int, input().split()))
x = list(sorted(set(a)))
n_sub = n * (n + 1) // 2
Li = 0
Ri = len(x)
while Ri > Li + 1:
    i = (Li + Ri) // 2
    xi = x[i]
    UorD = [1 if ak >= xi else -1 for ak in a]
    cnt_sum = [0] * (2 * n + 1)
    cumsum = 0
    cnt_sum[cumsum + n] = 1
    judge = 0
    s = 0
    for uk in UorD:
        cumsum += uk
        if uk == 1:
            s += cnt_sum[cumsum + n] + 1
        else:
            s -= cnt_sum[cumsum + n + 1] - 1
        cnt_sum[cumsum + n] += 1
        judge += s
        if judge >= n_sub // 2:
            Li = i
            break
    else:
        Ri = i
print(x[Li])

Buggy python submission (verdict: Time Limit Exceeded):
def update(i, x):
    while i < n:
        bit[i] += x
        i += i & -i


def getsum(i):
    s = 0
    while i:
        s += bit[i]
        i -= i & -i
    return s


n = int(input())
a = list(map(int, input().split()))
x = list(sorted(set(a)))

Li = -1
Ri = len(x) - 1
i = (Li + Ri) // 2
bit = [0] * (n + 1)
xi = x[i]
for ai, ak in enumerate(a):
    update(ai + 1, (ak > xi) * 2 - 1)
lr = [0] * n

while 1:
    M = 0
    for r in range(n):
        lr[r] = tmp = getsum(r + 1)
        M += (tmp >= 0) * 2 - 1
    for l in range(1, n):
        for r in range(l, n):
            lr[r] = tmp = lr[r] - lr[l - 1]
            M += (tmp >= 0) * 2 - 1
    if M >= 0:
        Li = i
    else:
        Ri = i
    if Li + 1 == Ri: break
    pi = i
    i = (Li + Ri) // 2
    if i < pi:
        s = x[i + 1]
        b = x[pi]
        dt = 2
    else:
        s = x[pi + 1]
        b = x[i]
        dt = -2
    for ai, ak in enumerate(a):
        if s <= ak <= b:
            update(ai + 1, dt)
print(x[Ri])


Fixed submission:
n = int(input())
a = list(map(int, input().split()))
x = list(sorted(set(a)))
n_sub = n * (n + 1) // 2
Li = 0
Ri = len(x)
while Ri > Li + 1:
    i = (Li + Ri) // 2
    xi = x[i]
    UorD = [1 if ak >= xi else -1 for ak in a]
    cnt_sum = [0] * (2 * n + 1)
    cumsum = 0
    cnt_sum[cumsum + n] = 1
    judge = 0
    s = 0
    for uk in UorD:
        cumsum += uk
        if uk == 1:
            s += cnt_sum[cumsum + n] + 1
        else:
            s -= cnt_sum[cumsum + n + 1] - 1
        cnt_sum[cumsum + n] += 1
        judge += s
        if judge >= n_sub // 2:
            Li = i
            break
    else:
        Ri = i
print(x[Li])

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
x = list(sorted(set(a)))
Li = -1
Ri = len(x) - 1
while Li + 1 < Ri:
    i = (Li + Ri) // 2
    xi = x[i]
    lr = []
    s = 0
    M = 0
    for ak in a:
        s += (ak > xi) * 2 - 1
        lr += [s]
        M += (s >= 0) * 2 - 1
    for l in range(1, n):
        for r in range(l, n):
            lr[r] -= lr[l - 1]
            M += (lr[r] >= 0) * 2 - 1
    if M >= 0:
        Li = i
    else:
        Ri = i
print(x[Ri])


Fixed submission:
n = int(input())
a = list(map(int, input().split()))
x = list(sorted(set(a)))
n_sub = n * (n + 1) // 2
Li = 0
Ri = len(x)
while Ri > Li + 1:
    i = (Li + Ri) // 2
    xi = x[i]
    UorD = [1 if ak >= xi else -1 for ak in a]
    cnt_sum = [0] * (2 * n + 1)
    cumsum = 0
    cnt_sum[cumsum + n] = 1
    judge = 0
    s = 0
    for uk in UorD:
        cumsum += uk
        if uk == 1:
            s += cnt_sum[cumsum + n] + 1
        else:
            s -= cnt_sum[cumsum + n + 1] - 1
        cnt_sum[cumsum + n] += 1
        judge += s
        if judge >= n_sub // 2:
            Li = i
            break
    else:
        Ri = i
print(x[Li])

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
x = list(sorted(set(a)))
Li = 0
Ri = len(x) - 1
while Li + 1 < Ri:
    i = (Li + Ri) // 2
    xi = x[i]
    a1 = [(ak > xi) * 2 - 1 for ak in a]
    lr = []
    s = 0
    M = 0
    for a1k in a1:
        s += a1k
        lr += [s]
        M += (s >= 0) * 2 - 1
    for l in range(1, n):
        for r in range(l, n):
            lr[r] -= lr[l - 1]
            M += (lr[r] >= 0) * 2 - 1
    if M >= 0:
        Li = i
    else:
        Ri = i
print(x[Ri])


Fixed submission:
n = int(input())
a = list(map(int, input().split()))
x = list(sorted(set(a)))
n_sub = n * (n + 1) // 2
Li = 0
Ri = len(x)
while Ri > Li + 1:
    i = (Li + Ri) // 2
    xi = x[i]
    UorD = [1 if ak >= xi else -1 for ak in a]
    cnt_sum = [0] * (2 * n + 1)
    cumsum = 0
    cnt_sum[cumsum + n] = 1
    judge = 0
    s = 0
    for uk in UorD:
        cumsum += uk
        if uk == 1:
            s += cnt_sum[cumsum + n] + 1
        else:
            s -= cnt_sum[cumsum + n + 1] - 1
        cnt_sum[cumsum + n] += 1
        judge += s
        if judge >= n_sub // 2:
            Li = i
            break
    else:
        Ri = i
print(x[Li])