Problem:
 Score : 700 points    Problem Statement We will define the median of a sequence b of length M , as follows:   Let b' be the sequence obtained by sorting b in non-decreasing order. Then, the value of the (M / 2 + 1) -th element of b' is the median of b . Here, / is integer division, rounding down.   For example, the median of (10, 30, 20) is 20 ; the median of (10, 30, 20, 40) is 30 ; the median of (10, 10, 10, 20, 30) is 10 .  Snuke comes up with the following problem.  You are given a sequence a of length N .
For each pair (l, r) ( 1 \leq l \leq r \leq N ), let m_{l, r} be the median of the contiguous subsequence (a_l, a_{l + 1}, ..., a_r) of a .
We will list m_{l, r} for all pairs (l, r) to create a new sequence m .
Find the median of m .      Constraints  1 \leq N \leq 10^5  a_i is an integer.  1 \leq a_i \leq 10^9         Input Input is given from Standard Input in the following format:  N  a_1  a_2  ...  a_N       Output Print the median of m .        Sample Input 1 3
10 30 20      Sample Output 1 30  The median of each contiguous subsequence of a is as follows:   The median of (10) is 10 .  The median of (30) is 30 .  The median of (20) is 20 .  The median of (10, 30) is 30 .  The median of (30, 20) is 30 .  The median of (10, 30, 20) is 20 .   Thus, m = (10, 30, 20, 30, 30, 20) and the median of m is 30 .       Sample Input 2 1
10      Sample Output 2 10       Sample Input 3 10
5 9 5 9 8 9 3 5 4 3      Sample Output 3 8

Solution (Python):
def d_median_of_medians(N, A):
    class BIT(object):
        """Binary Indexed Tree (1-indexed)"""

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

        def sum(self, index):
            """tree[1]からtree[index]までの和を計算"""
            ret = 0
            while index > 0:
                ret += self.tree[index]
                index -= index & (-index)
            return ret

        def add(self, index, value):
            """tree[index]にvalueを加算"""
            while index <= self.size:
                self.tree[index] += value
                index += index & (-index)

    def is_accepted(x):
        """
        A[l]からA[r]までの要素の中央値がx以上か。すなわち、A[l]からA[r]までの
        要素のうちx以上であるものが (N*(N+1)/2)/2 個以上か
        """
        from itertools import accumulate
        from math import ceil
        a_larger_x = [(1 if a >= x else -1) for a in A]  
        cumsum = list(accumulate(a_larger_x))

        ans = 0
        a_larger_x_sorted = {a: k for k, a in enumerate(sorted(cumsum), 1)}
        bit = BIT(N)
        for c in cumsum:
            ans += bit.sum(a_larger_x_sorted[c]) + int(c >= 0)
            bit.add(a_larger_x_sorted[c], 1)
        return True if ans >= ceil((N * (N + 1)) / 4) else False

    
    
    accept = 0
    reject = 10**9 + 1  
    while reject - accept > 1:
        mid = (accept + reject) // 2
        if is_accepted(mid):
            accept = mid
        else:
            reject = mid
    return accept

N = int(input())
A = [int(i) for i in input().split()]
print(d_median_of_medians(N, A))

Solution (Python):
import math

n = int(input())
lst = list(map(int, input().split()))
 
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
 
            
def judge(x, lst, n):
 
    length = len(lst)
    all_pair = (length*(length-1) // 2) + length
    
    lst_r = [-1 if i < x else 1 for i in lst]
    lst_accum = []
    a = 0
    for i in lst_r:
        a += i
        lst_accum.append(a)
    
    bit = Bit(n)
    lst_accum_sorted = {b: i for i, b in enumerate(sorted(lst_accum), start=1)}
    count = 0
    for j, b in enumerate(lst_accum):
        count += bit.sum(lst_accum_sorted[b]) + (b >= 0)
        bit.add(lst_accum_sorted[b], 1)
        
    if count >= math.ceil(all_pair/2):
        return True
    else:
        return False
 
    
sorted_lst = sorted(lst)
low = 0
high = len(lst) - 1
while high - low >1:
    t = (low+high) // 2
    i = sorted_lst[t]
    if judge(i, lst, n):
        low = t
    else:
        high = t
        
print(sorted_lst[high]) if judge(sorted_lst[high], lst, n) else print(sorted_lst[low])

Solution (Python):
from itertools import accumulate
from math import ceil
 
N = int(input())
A = list(map(int, input().split()))
 
if N == 1:
    print(A[0])
    exit()
 
 
class BinaryIndexedTree:
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= (i & -i)
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.bit[i] += x
            i += (i & -i)
 
    def reset(self):
        self.bit = [0] * (self.size + 1)
 
 
BIT = BinaryIndexedTree(N)  
lo, hi = -1, 10 ** 9 + 1
while hi - lo > 1:
    
    X = (hi + lo) // 2
 
    
    Binary = [(1 if a >= X else -1) for a in A]
 
    
    Binary = list(accumulate(Binary))
 
    
    BIT.reset()
 
    
    inversion = 0
    Binary_sorted = {b: i for i, b in enumerate(sorted(Binary), start=1)}
    for j, b in enumerate(Binary):
        inversion += BIT.sum(Binary_sorted[b]) + (b >= 0)
        BIT.add(Binary_sorted[b], 1)
 
    if inversion >= ceil((N * (N + 1) / 2) / 2):
        lo = X
    else:
        hi = X
 
print(lo)

Solution (Python):
N = int(input())
A = [int(i) for i in input().split()]
AS = sorted(list(set(A)))

def f(x):
    B = [((x<=a)<<1)-1 for a in A]
    C = [N]
    [C.append(C[-1]+b) for b in B]

    r = 0
    Bit = [0] * (2*N+1)

    for i,c in enumerate(C):
        t=c-1
        while(t>0):
            r += Bit[t]
            t -= t&-t
        t=c-1
        while(t<=2*N+1):
            Bit[t] += 1
            t += t&-t
    return(r>=N*(N+1)//4)

l = 0
r = len(AS)-1
while l != r:
    if f(AS[(l+r+1)//2]):
        l = (l+r+1)//2
    else:
        r = (((l+r+1)//2)-1)
print(AS[r])

Solution (Python):
from itertools import accumulate
from math import ceil

class BIT():
    def __init__(self,n):
        self.size=n
        self.bit=[0]*(n+1)
    def add(self,i,x):
        while i<=self.size:
            self.bit[i]+=x
            i+=i&-i
    def sum(self,i):
        s=0
        while i>0:
            s+=self.bit[i]
            i-=i&-i
        return s
    def reset(self):
        self.bit=[0]*(self.size+1)

n=int(input())
A=list(map(int,input().split()))
bit=BIT(n+1)
l,r=0,10**9+1
while r-l>1:
    mid=(l+r)//2
    B=[(1 if a>=mid else -1) for a in A]
    B=[0]+list(accumulate(B))
    cnt=0
    B_sorted={b: i for i,b in enumerate(sorted(B),start=1)}
    bit.reset()
    for b in B:
        cnt+=bit.sum(B_sorted[b])
        bit.add(B_sorted[b],1)
    if cnt>=ceil((n*(n+1)//2)/2):
        l=mid
    else:
        r=mid
print(l)

Solution (Python):
import math
 
n = int(input())
a = [int(i) for i in input().split(" ")]

m = n * (n + 1) // 2
 
class BIT:
    def __init__(self, n):
        self.t = [0] * (n + 1)
    
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.t[i]
            i -= (i & -i)
        return s
    
    def add(self, i, v):
        while i < len(self.t):
            self.t[i] += v
            i += (i & -i)
            
def count(s):
    s_min = min(s)
    b = BIT(max(s) - s_min + 1)
    t = [0] * len(s)
    for j in range(0, len(s)):
        t[j] = b.sum(s[j] - s_min + 1)
        b.add(s[j] - s_min + 1, 1)
    return sum(t)
            
def bs(l, r):
    if l == r:
        return l
    else:
        h = math.ceil((l + r) / 2)
        
        ab = [-1 if a[i] < h else 1 for i in range(0, n)]
        s = [0] * (n + 1)
        
        for i in range(1, n + 1):
            s[i] = s[i - 1] + ab[i - 1]
            
        if count(s) >= math.ceil(m / 2):
            return bs(h, r)
        else:
            return bs(l, h - 1)
        
print(bs(min(a), max(a)))

Solution (Python):

def median_of_medians(N: int, A: list)->int:
    def search(c):
        bar = N
        r = 0
        res_nega = 0
        dp_arr = [0]*(2*N+1)
        for i in range(N):
            dp_arr[bar] += 1
            if A[i] < c:
                r += dp_arr[bar]
                bar += 1
            else:
                r -= (dp_arr[bar-1])
                bar -= 1
            res_nega += r
        return res_nega

    
    a_sorted = sorted(A)
    left = 0
    right = N
    mid = N // 2
    C = N*(N+1) // 2
    while True:
        if search(a_sorted[mid]) <= C // 2:
            if mid == N-1:
                break
            elif search(a_sorted[mid+1]) > C // 2:
                break
            else:
                left = mid
                mid = (mid + right) // 2
        else:
            right = mid + 1
            mid = (mid + left) // 2

    return a_sorted[mid]


if __name__ == "__main__":
    N = int(input())
    A = [int(s) for s in input().split()]
    ans = median_of_medians(N, A)
    print(ans)

Solution (Python):
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

n = int(input())
a = list(map(int, input().split()))
def med(x):
    cum = [0] * (n+1)
    for i in range(n):
        if a[i] >= x:
            cum[i+1] = cum[i] + 1
        else:
            cum[i+1] = cum[i] - 1
    m = min(cum)
    for i in range(n+1):
        cum[i] -= m - 1
    zb = Bit(max(cum))
    ret = 0
    for j in range(n+1):
        ret += zb.sum(cum[j])
        zb.add(cum[j], 1)
    return ret
b = sorted(a)
l = 0
r = n
while(r - l > 1):
    mid = (l + r + 1) // 2
    if 2 * med(b[mid]) >= n * (n+1) // 2:
        l = mid
    else:
        r = mid
print(b[l])

Solution (Python):
n = int(input())
a = list(map(int, input().split()))

def check(x):
    b = n
    r = 0
    y = 0
    D = [0]*(2*n+1)
    for i in range(n):
        D[b] += 1
        if a[i] < x:
            r += D[b]
            b += 1
        else:
            b -= 1
            r -= D[b]
        y += r
    return y

alpha = sorted(a)
l, r = 0, n
m, c = n//2, n*(n+1)//2
while True:
    if check(alpha[m]) <= c//2:
        if m == n-1:
            break
        elif check(alpha[m+1]) > c//2:
            break
        else:
            l, m = m, (m+r)//2
    else:
        m, r = (m+l)//2, m+1
        
print(alpha[m])

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

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            
            
            i -= i & -i
        return s

    
    
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

def invnumber(n, S):
    bit = Bit(2*n+1)
    invs = 0
    for i in range(n):
        s = S[i]+n 
        invs += bit.sum(s) 
        bit.add(s, 1)
    return invs

n = int(input())
a = list(map(int, input().split()))
r = max(a)+1
l = 0
c = (n*(n+1)//2+1)//2
while r-l > 1:
    m = (l+r)//2
    S = [0]*(n+1)
    for i in range(1, n+1):
        if a[i-1] >= m:
            S[i] = S[i-1] + 1
        else:
            S[i] = S[i-1] - 1
    if invnumber(n+1, S) >= c:
        l = m
    else:
        r = m
print(l)

Solution (Python):

from bisect import bisect_left
from math import ceil
import sys
if sys.version_info[0:2] >= (3, 3):
    from collections.abc import Sequence
else:
    from collections import Sequence


class LazySequence(Sequence):
    def __init__(self, f, n):
        self.f = f
        self.n = n

    def __len__(self):
        return self.n

    def __getitem__(self, i):
        if not (0 <= i < self.n):
            raise IndexError
        return self.f(i)


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

    def __len__(self):
        return self.size

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, v):
        while i <= self.size:
            self.tree[i] += v
            i += i & -i


N = int(input())
a = [0] + [int(s) for s in input().split()]



def count_lr(x):
    s = [0] * (N + 1)
    for i in range(1, N + 1):
        s[i] = s[i - 1] + (1 if a[i] >= x else -1)

    ss = sorted(set(s))
    ind = {v: i + 1 for i, v in enumerate(ss)}

    b = Bit(N + 10)
    count = 0
    for i in range(N + 1):
        j = ind[s[i]]
        count += b.sum(j)
        b.add(j, 1)

    return count




counts = LazySequence(lambda i: count_lr(10 ** 9 - i), 10 ** 9 + 1)
ans = 10 ** 9 - bisect_left(counts, ceil(N * (N + 1) / 4))
print(ans)

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate


class BIT(object):
    def __init__(self, size):
        self.size = size+1
        self.bitree = [0]*self.size
        
    def addval(self, idx:int, val:int):
        while idx < self.size:
            self.bitree[idx] += val
            idx += idx&(-idx)
            
    def getsum(self, idx:int):
        ret = 0
        while idx > 0:
            ret += self.bitree[idx]
            idx -= idx&(-idx)
            
        return ret
    
    def reset(self):
        self.bitree = [0]*self.size
        

def findInv(arr:list, med:int):
    arrbin = [-1 if ai < med else 1 for ai in arr]
    arrcum = [0] + list(accumulate(arrbin))
    arrcummin = abs(min(arrcum))
    arrcumpos = [arrcum_i + arrcummin + 1 for arrcum_i in arrcum]
    
    bitree = BIT(max(arrcumpos))
    inv = 0
    for i,ai in enumerate(arrcumpos):
        inv += (i - bitree.getsum(ai))
        bitree.addval(ai, 1)
        
    return inv


def binsearch(arr:list):
    low = 0
    high = max(arr) + 1
    n = len(arr)
    threshould = n*(n+1)//4
    
    while high-low > 1:
        mid = (high+low) // 2

        if findInv(arr, mid) <= threshould:
            low = mid
            
        else:
            high = mid
            
    return low        

n = ni()
a = list(li())

print(binsearch(a))

Solution (Python):
from itertools import accumulate
from math import ceil

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


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

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= (i & -i)
        return s

    def add(self, i, x):
        while i <= self.size:
            self.bit[i] += x
            i += (i & -i)

    def reset(self):
        self.bit = [0] * (self.size + 1)


BIT = BinaryIndexedTree(N + 1)
ng, ok = 10 ** 9 + 1, 0
while abs(ok - ng) > 1:
    X = (ok + ng) // 2

    B = [(1 if a >= X else -1) for a in A]
    B = [0] + list(accumulate(B))

    tmp = 0
    B_sorted = {b: i for i, b in enumerate(sorted(B), start=1)}
    BIT.reset()
    for j, b in enumerate(B):
        tmp += BIT.sum(B_sorted[b])
        BIT.add(B_sorted[b], 1)

    if tmp >= ceil((N * (N + 1) // 2) / 2):
        ok = X
    else:
        ng = X

print(ok)

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


class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0] * n

    def add(self, k, x):
        while k < self.n:
            self.data[k] += x
            k += k & -k

    def get(self, k):
        s = 0
        while k > 0:
            s += self.data[k]
            k -= k & -k

        return s

    def init(self, n):
        self.n = n
        self.data = [0] * n


left, right = 0, 10 ** 9 + 5
bit = BIT(N)
while right - left > 1:
    x = (right + left) // 2

    S = [0] * (N + 1)
    for i in range(N):
        if A[i] >= x:
            S[i + 1] = S[i] + 1
        else:
            S[i + 1] = S[i] - 1

    p = abs(min(S)) + 1
    for i in range(N + 1):
        S[i] += p
    q = max(S) + 1
    bit.init(q)
    num = 0
    for i in S:
        num += bit.get(i)
        bit.add(i, 1)

    if num * 2 >= N * (N + 1) // 2:
        left = x
    else:
        right = x

print(left)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
data = [0] * (N + 1)


def add(k, x, M):
    while k <= M:
        data[k] += x
        k += k & -k


def get(k):
    s = 0
    while k > 0:
        s += data[k]
        k -= k & -k

    return s


left, right = 0, 10 ** 9 + 1
while right - left > 1:
    x = (left + right) // 2

    S = [0] * (N + 1)
    for i in range(N):
        if A[i] >= x:
            S[i + 1] = S[i] + 1
        else:
            S[i + 1] = S[i] - 1

    a = abs(min(S)) + 1
    for i in range(N + 1):
        S[i] += a

    b = max(S)
    data = [0] * (b + 1)
    num = 0
    for i in S:
        num += get(i)
        add(i, 1, b)

    if num * 2 >= (N * (N + 1) // 2):
        left = x
    else:
        right = x

print(left)

Solution (Python):
from itertools import accumulate
from math import ceil
N = int(input())
A = list(map(int, input().split()))


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

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= (i & -i)
        return s

    def add(self, i, x):
        while i <= self.size:
            self.bit[i] += x
            i += (i & -i)

    def reset(self):
        self.bit = [0] * (self.size + 1)


ok, ng = 0, 10 ** 9 + 1
BIT = BinaryIndexedTree(N + 1)
while abs(ok - ng) > 1:
    X = (ok + ng) // 2
    B = [(1 if a >= X else -1) for a in A]
    B = [0] + list(accumulate(B))
    B_sorted = {b: i for i, b in enumerate(sorted(B), start=1)}

    tmp = 0
    BIT.reset()
    for j, b in enumerate(B):
        tmp += BIT.sum(B_sorted[b])
        BIT.add(B_sorted[b], 1)

    if tmp >= ceil((N * (N + 1) / 2) / 2):
        ok = X
    else:
        ng = X

print(ok)

Solution (Python):
from itertools import accumulate
from math import ceil
N = int(input())
A = list(map(int, input().split()))


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

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= (i & -i)
        return s

    def add(self, i, x):
        while i <= self.size:
            self.bit[i] += x
            i += (i & -i)

    def reset(self):
        self.bit = [0] * (self.size + 1)


lo, hi = -1, 10 ** 9 + 1
BIT = BinaryIndexedTree(N + 1)
while hi - lo > 1:
    X = (hi + lo) // 2
    B = [(1 if a >= X else -1) for a in A]
    B = [0] + list(accumulate(B))
    B_sorted = {b: i for i, b in enumerate(sorted(B), start=1)}

    tmp = 0
    BIT.reset()
    for j, b in enumerate(B):
        tmp += BIT.sum(B_sorted[b])
        BIT.add(B_sorted[b], 1)

    if tmp >= ceil((N * (N + 1) / 2) / 2):
        lo = X
    else:
        hi = X

print(lo)

Solution (Python):
def add(B,a,n):
    x = a
    while x <= n:
        B[x] += 1
        x += x&(-x)

def sums(B,a):
    x = a
    S = 0
    while x != 0:
        S += B[x]
        x -= x&(-x)
    return S


def invnumber(n, S):
    B = [0]*(n*2 + 1)
    invs = 0
    for i in range(n):
        s = S[i] + n
        invs += sums(B, s)
        add(B, s, n*2)
    return invs

N = int( input())
A = list( map( int, input().split()))
R = max(A)+1
L = 0
c = (N*(N+1)//2 + 1)//2
while R - L > 1:
    M = (R+L)//2
    S = [0]*(N+1)
    for i in range(1,N+1):
        if A[i-1] >= M:
            S[i] = S[i-1] + 1
        else:
            S[i] = S[i-1] - 1
    if invnumber(N+1,S) >= c:
        L = M
    else:
        R = M
print(L)

Solution (Python):
from itertools import accumulate
from math import ceil
N = int(input())
A = list(map(int, input().split()))


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

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= (i & -i)
        return s

    def add(self, i, x):
        while i <= self.size:
            self.bit[i] += x
            i += (i & -i)

    def reset(self):
        self.bit = [0] * (self.size + 1)



BIT = BinaryIndexedTree(N)

lo, hi = -1, max(A) + 1  
while hi - lo > 1:
    m = (hi + lo) // 2

    
    binary = [(1 if a >= m else -1) for a in A]
    binary = list(accumulate(binary))

    
    BIT.reset()

    
    tmp = 0

    
    binary_sorted = {b: i for i, b in enumerate(sorted(binary), start=1)}
    ans = 0
    for j, b in enumerate(binary):
        tmp += BIT.sum(binary_sorted[b]) + (b >= 0)
        BIT.add(binary_sorted[b], 1)

    
    if tmp >= ceil(((N * (N + 1)) / 2) / 2):
        lo = m
    else:
        hi = m

print(lo)

Solution (Python):
from itertools import accumulate
from math import ceil

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

if N == 1:
    print(A[0])
    exit()


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

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= (i & -i)
        return s

    def add(self, i, x):
        while i <= self.size:
            self.bit[i] += x
            i += (i & -i)

    def reset(self):
        self.bit = [0] * (self.size + 1)


BIT = BinaryIndexedTree(N)  
lo, hi = -1, 10 ** 9 + 1
while hi - lo > 1:
    
    X = (hi + lo) // 2

    
    Binary = [(1 if a >= X else -1) for a in A]

    
    Binary = list(accumulate(Binary))

    
    BIT.reset()

    
    inversion = 0
    Binary_sorted = {b: i for i, b in enumerate(sorted(Binary), start=1)}
    for j, b in enumerate(Binary):
        inversion += BIT.sum(Binary_sorted[b]) + (b >= 0)
        BIT.add(Binary_sorted[b], 1)

    if inversion >= ceil((N * (N + 1) / 2) / 2):
        lo = X
    else:
        hi = X

print(lo)

Solution (Python):
n = int(input())
A = list(map(int, input().split()))

def search(x):
    b = n
    r = 0
    y = 0
    D = [0]*(2*n+1)
    for i in range(n):
        D[b] += 1
        if A[i] < x:
            r += D[b]
            b += 1
        else:
            b -= 1
            r -= D[b]   
        y += r
    return y

S = sorted(A)
l = 0
r = n
m = n // 2
c = n * (n + 1) // 2

while True:
    if search(S[m]) <= c // 2:
        if m == n - 1:
            break
        elif search(S[m + 1]) > c // 2:
            break
        else:
            l = m
            m = (m + r) // 2
    else:
        r = m + 1
        m = (m + l) // 2
        
print(S[m])

Solution (Python):
n = int(input())
a = list(map(int, input().split()))

if n == 1:
    print(a[0])
    exit()

b = list(sorted(set(a)))

def count_inversion(ans):
    s = [0 for _ in range(2 * n + 2) ]

    def bit_add(i):
        x = i
        while x < 2 * n:
            s[x] += 1
            x += x & -x

    def bit_sum(i):
        x = i
        ret = 0
        while x > 0:
            ret += s[x]
            x -= x & -x
        return ret

    temp = [n for _ in range(n + 1)]
    temp[0] = n + 1
    for i in range(n):
        if a[i] >= b[ans]:
            temp[i + 1] = temp[i] + 1
        else:
            temp[i + 1] = temp[i] - 1
    res = 0
    for i in range(n + 1):
        x = temp[i]
        res += bit_sum(x)
        bit_add(x)
    return res

m = n * (n + 1) // 2

ans = 0

l = 0
r = len(b)
while 1:
    ans = (l + r) // 2
    if count_inversion(ans) * 2 >= m:
        l = ans
    else:
        r = ans
    if r - l <= 1:
        ans = l
        break

print(b[ans])

Solution (Python):
N = int(input())
A = [int(_) for _ in input().split()]


def sub_problem(x):
    S = [0] * (N + 1)
    for i in range(N):
        S[i + 1] = S[i] + 1 if A[i] >= x else S[i] - 1

    geta = abs(min(S)) + 1
    for i in range(N + 1):
        S[i] += geta

    forward = 0
    size = max(S)
    bit = [0] * (size + 1)
    for s in S:
        i = s
        while i > 0:
            forward += bit[i]
            i -= i & -i

        i = s
        while i <= size:
            bit[i] += 1
            i += i & -i

    return forward >= (M + 1) // 2


M = N * (N + 1) // 2  
sorted_A = sorted(A)

inf = 0
sup = N
while sup - inf > 1:
    mid = (sup + inf) // 2
    x = sorted_A[mid]

    if sub_problem(x):
        inf = mid
    else:
        sup = mid

print(sorted_A[inf])

Solution (Python):
N = int(input())
A = [int(_) for _ in input().split()]

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

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

def sub_problem(x):
    S = [0] * (N + 1)
    for i in range(N):
        S[i + 1] = S[i] + 1 if A[i] >= x else S[i] - 1

    geta = abs(min(S)) + 1
    for i in range(N + 1):
        S[i] += geta

    forward = 0
    bit = BIT(max(S))
    for s in S:
        forward += bit.sum(s)
        bit.add(s, 1)

    return forward >= M // 2 

M = N * (N + 1) // 2  
sorted_A = sorted(A)

inf = 0
sup = N
while sup - inf > 1:
    mid = (sup + inf) // 2
    x = sorted_A[mid]

    if sub_problem(x):
        inf = mid
    else:
        sup = mid

print(sorted_A[inf])

Solution (Python):
N = int(input())
A = [int(_) for _ in input().split()]

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

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

def sub_problem(x):
    S = [0] * (N + 1)
    for i in range(N):
        S[i + 1] = S[i] + 1 if A[i] >= x else S[i] - 1

    geta = abs(min(S)) + 1
    for i in range(N + 1):
        S[i] += geta

    forward = 0
    bit = BIT(max(S))
    for s in S:
        forward += bit.sum(s)
        bit.add(s, 1)

    return forward >= (M + 1) // 2

M = N * (N + 1) // 2  
sorted_A = sorted(A)

inf = 0
sup = N
while sup - inf > 1:
    mid = (sup + inf) // 2
    x = sorted_A[mid]

    if sub_problem(x):
        inf = mid
    else:
        sup = mid

print(sorted_A[inf])

Solution (Python):
N = int(input())
A = [int(_) for _ in input().split()]


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

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


M = N * (N + 1) // 2  
sorted_A = sorted(A)

inf = 0
sup = max(A) + 1
while sup - inf > 1:
    x = (sup + inf) // 2

    S = [0] * (N + 1)
    for i in range(N):
        if A[i] >= x:
            S[i + 1] = S[i] + 1
        else:
            S[i + 1] = S[i] - 1

    min_value = min(S)
    for i in range(N + 1):
        S[i] += abs(min_value) + 1

    forward = 0
    bit = BIT(max(S))
    for s in S:
        forward += bit.sum(s)
        bit.add(s, 1)

    if forward >= (M + 1) // 2:
        inf = x
    else:
        sup = x

for a in reversed(sorted_A):
    if inf >= a:
        print(a)
        break

Solution (Python):
N = int(input())
src = list(map(int,input().split()))

cands = list(sorted(set(src)))

def enough(i):
    bit = [0] * (2*N+10)
    def bit_add(a,w):
        x = a
        while x <= (2*N+9):
            bit[x] += w
            x += (x & -x)
    def bit_sum(a):
        x = a
        ret = 0
        while x > 0:
            ret += bit[x]
            x -= (x & -x)
        return ret

    cums = [0]
    for a in src:
        tmp = 1 if a >= cands[i] else -1
        cums.append(cums[-1] + tmp)

    cnt = 0
    for i in range(N+1):
        a = cums[i] + N+5
        cnt += bit_sum(a)
        bit_add(a, 1)
    return cnt*2 >= N*(N+1)//2

ok = 0
ng = len(cands)
while ng - ok > 1:
    m = (ok+ng)//2
    if enough(m):
        ok = m
    else:
        ng = m
print(cands[ok])

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

A_sort=sorted(A)
ANSMIN=0
ANSMAX=N-1
cums=[None]*(N+1)

def midup(x):
    cums[0]=0
    for i in range(N):
        if A[i]>=x:
            cums[i+1]=cums[i]+1
        else:
            cums[i+1]=cums[i]-1

    MINS=min(cums)
    MAXS=max(cums)

    

    bitlist=[0 for i in range(MAXS-MINS+2)]

    NUM=0

    for i in range(N+1):
        bitobje=cums[i]-MINS+1
        

        x=bitobje
        while x!=0:
            NUM+=bitlist[x]
            x-=(x&(-x))

        while bitobje<=MAXS-MINS+1:
            bitlist[bitobje]+=1
          
            bitobje+=(bitobje &(-bitobje))

    if NUM>=(N+1)*N//2/2:
        return 1
    else:
        return 0


while True:
    candi=A_sort[(ANSMIN+ANSMAX)//2]

    if midup(candi)==1:
        ANSMIN=(ANSMIN+ANSMAX)//2
    else:
        ANSMAX=(ANSMIN+ANSMAX)//2

    if A_sort[ANSMIN]==A_sort[ANSMAX]:
        print(A_sort[ANSMIN])
        break
    if ANSMIN+1==ANSMAX:
        if midup(A_sort[ANSMAX])==1:
            print(A_sort[ANSMAX])
            break
        else:
            print(A_sort[ANSMIN])
            break

Solution (Python):



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




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以上のものの個数"""

    
    b = [-1 if e < x else 1 for e in a]

    
    S = [0]
    for e in b:
        S.append(S[-1] + e)

    
    
    return mergesort(S, 0, len(S))


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)