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):
n = int(input())
a = 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):
        if not (0 <= i < self.size): raise ValueError("error!")
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

def search(x):
    l = [1 if i >= x else -1 for i in a]
    c = [n]
    for i in range(n):
        c.append(c[-1]+l[i])

    count = 0
    bit = Bit(2*n+1)
    for i in c:
        count += bit.sum(i+1)
        bit.add(i,1)
    
    return x,count

k = (n*(n+1)/2+1)//2
le = 0
ri = max(a)+1

while ri > le + 1:
    m = (ri+le)//2
    ans,count = search(m)

    if count >= k:
        le = m
    else:
        ri = m
print(le)

Solution (Python):


import sys
from itertools import accumulate
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  


class BIT:
    def __init__(self,init_value):
        self.n = len(init_value)
        self.tree = [0]*(self.n+1)
        for i in range(1,self.n+1):
            x = init_value[i-1]
            while i <= self.n:
                self.tree[i] += x
                i += i & (-i)

    def update(self,i,x):  
        while i <= self.n:
            self.tree[i] += x
            i += i & (-i)
        return

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


N = I()
A = LI()
C = sorted(list(set(A)))
dict_A = {}  
dict_C = {}  
for i in range(1,len(C)+1):
    dict_C[i] = C[i-1]
    dict_A[C[i-1]] = i
A = [dict_A[a] for a in A]


def f(x):  
    B = [0] + [1 if A[i] >= x else -1 for i in range(N)]
    B = list(accumulate(B))
    B = [b+N+1 for b in B]  
    
    bit = BIT([0]*(2*N+2))
    count = 0
    for i in range(N+1):
        b = B[i]
        count += bit.query(b)
        bit.update(b,1)
    if count >= (N*(N+1)+3)//4:
        return True
    return False


ok = 1
ng = 10**5+1
while ok+1 < ng:
    mid = (ok+ng)//2
    if f(mid):
        ok = mid
    else:
        ng = mid

print(dict_C[ok])

Solution (Python):
import sys
from itertools import accumulate
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  


class BIT:
    def __init__(self,init_value):
        self.n = len(init_value)
        self.tree = [0]*(self.n+1)
        for i in range(1,self.n+1):
            x = init_value[i-1]
            while i <= self.n:
                self.tree[i] += x
                i += i & (-i)

    def update(self,i,x):  
        while i <= self.n:
            self.tree[i] += x
            i += i & (-i)
        return

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


N = I()
A = LI()


def f(x):  
    B = [0] + [1 if A[i] >= x else -1 for i in range(N)]
    B = list(accumulate(B))
    B = [b+N+1 for b in B]  
    
    bit = BIT([0]*(2*N+2))
    count = 0
    for i in range(N+1):
        b = B[i]
        count += bit.query(b)
        bit.update(b,1)
    if count >= (N*(N+1)+3)//4:
        return True
    return False


ok = 1
ng = 10**9+1
while ok+1 < ng:
    mid = (ok+ng)//2
    if f(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Solution (Python):
import sys
from itertools import accumulate
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  


class BIT:
    def __init__(self,init_value):
        self.n = len(init_value)
        self.tree = [0]*(self.n+1)
        for i in range(1,self.n+1):
            x = init_value[i-1]
            while i <= self.n:
                self.tree[i] += x
                i += i & (-i)

    def update(self,i,x):  
        while i <= self.n:
            self.tree[i] += x
            i += i & (-i)
        return

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


N = I()
A = LI()


def f(x):  
    B = [0] + [1 if A[i] >= x else -1 for i in range(N)]
    B = list(accumulate(B))
    B = [b+N for b in B]
    
    bit = BIT([0]*(2*N+2))
    count = 0
    for i in range(N+1):
        b = B[i]
        count += bit.query(b+1)
        bit.update(b+1,1)
    return True if count >= (N*(N+1)+3)//4 else False


ok = 1
ng = 10**9+1
while ok+1 < ng:
    mid = (ok+ng)//2
    if f(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Solution (Python):
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])

Solution (Python):
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

"""
aiが数列mに何回出現するか，がわかれば良い？
左をa個，右をB個見たときに，M=a+B+1として，aiがM//2 +1番目なら良い．
→ai以上の要素が(M+1)//2個以上ある，かつ，此の性質を満たすものの中で最大の数である．
これ辛そう...

でも中央値を求めるのに二分探索は良いよな
結局，答えxの決めうち二分探索で，数列mの中でx以上の要素が何個あるかを知ることができれば解ける．
(x以上のものが(M+1)//2個以上ある中で最大のxを探したい)

つまり，a[l,r]のうち，中央値がx以上になるものはいくつありますか，をときたい
a[l,r]のうちx以上の要素を((r-l+1)+1)/2個以上含むものは何個あるか，がわかれば良いか
x以上ならば+1，そうでなければ-1として，区間の総和が0以上になる区間の個数を探す．
累積和で処理する，S_r-S_(l-1)が0以上ならばOK．このl,rの組を探すのはseg木でできるか，転倒数と同じ要領で．


"""
def main():
    class BIT:
        '''
        0-indexed
        '''
        def __init__(self, N):
            self.size = N
            self.tree = [0] * (N + 1)
            self.depth = N.bit_length()

        def _bitsum(self, i):
            ret = 0
            while i:
                ret += self.tree[i]
                i ^= i & -i
            return ret

        
        def sum(self, l, r=None):
            if r is None:
                return self._bitsum(l)
            else:
                return self._bitsum(r) - self._bitsum(l)

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

        def lower_bound(self, x):
            sum_ = 0
            pos = 0
            v = 1 << self.depth
            for i in range(self.depth, -1, -1):
                k = pos + v
                if k <= self.size and sum_ + self.tree[k] < x:
                    sum_ += self.tree[k]
                    pos += v
                v >>= 1
            return pos + 1, sum_

    N=I()
    A=LI()
    
    
    def calc(x):
        
        
        B=[0]*N
        for i in range(N):
            if A[i]>=x:
                B[i]=1
            else:
                B[i]=-1
                
        
        S=[0]*(N+1)
        for i in range(N):
            S[i+1]=S[i]+B[i]
            
        
        inf=10**6
        for i in range(N+1):
            S[i]=S[i]*inf+i
        S.sort()

            
        
        bit=BIT(N+1)
        res=0
        for i in range(N+1):
            s=S[i]
            ii=s%inf
            temp=bit.sum(0,ii)
            res+=temp
            bit.add(ii,1)
        return res
    
    A2=sorted(A)
    M=(N*N)//2
    ok=0
    ng=N
    
    def ch(x):
        cnt=calc(x)
        
        return cnt>=(M+1)//2

    while ng-ok>1:
        
        med=(ok+ng)//2
        x=A2[med]
        if ch(x):
            ok=med
        else:
            ng=med
        
            
    print(A2[ok])
                
        
    

main()

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
 
sortA = sorted(set(A)) + [float('inf')]
 
def isOk(n):
    x = sortA[n]
    count = [0 for _ in range(2 * N + 1)]
    count[N + 1] = 1
 
    i = N + 1
    s = 1
    result = 0
 
    for a in A:
        if a >= x:
            i += 1
            s += count[i]
        else:
            s -= count[i]
            i -= 1
        result += s
        count[i] += 1
        s += 1
 
    if result >= N * (N + 1) // 4:
        return False
    else:
        return True
 
 
left = 0
right = len(sortA) - 1
 
while right - left > 1:
    mid = (left + right ) // 2
 
    if isOk(mid):
        right = mid
    else:
        left = mid
 
print(sortA[left])

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
a2=sorted(set(a))
L=len(a2)
if n==1:print(a[0]);exit()
elif n==2:print(a[1]);exit()
ng=L
ok=0
while ng-ok>1:
    check=a2[(ok+ng)//2]
    cnt=0 
    idx=n
    cl=[0]*(2*n+1)
    cl[n]=1
    Ru=0
    for i in range(n):
        if a[i]<check:
            Ru-=cl[idx]-1
            idx-=1
        else:
            idx+=1
            Ru+=cl[idx]+1
        cnt += Ru
        cl[idx]+=1
    if cnt >= ((n+1)*n//2)//2:
        ok = (ok+ng)//2
    else:
        ng = (ok+ng)//2

print(a2[ok])

Solution (Python):
from math import ceil
from itertools import accumulate
n = int(input())
import math
import decimal
import collections
import itertools
import sys

def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
def unite(x, y):
    p = find(x)
    q = find(y)
    if p == q:
        return None
    if p > q:
        p,q = q,p
    par[p] += par[q]
    par[q] = p
def same(x, y):
    return find(x) == find(y)
def size(x):
    return -par[find(x)]
par = [-1 for i in range(n)]


def prime_numbers(x):
    if x < 2:
        return []
    prime_numbers = [i for i in range(x)]
    prime_numbers[1] = 0
    for prime_number in prime_numbers:
        if prime_number > math.sqrt(x):
            break
        if prime_number == 0:
            continue
        for composite_number in range(2 * prime_number, x, prime_number):
            prime_numbers[composite_number] = 0
    return [prime_number for prime_number in prime_numbers if prime_number != 0]
def is_prime(x):
    if x < 2:
        return False
    if x == 2 or x == 3 or x == 5:
        return True
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0:
        return False
    prime_number = 7
    difference = 4
    while prime_number <= math.sqrt(x):
        if x % prime_number == 0:
            return False
        prime_number += difference
        difference = 6 - difference
    return True

mod = 10 ** 9 + 7
def comb(n, r):
    if n < r:return 0
    if n < 0 or r < 0:return 0
    return fa[n] * fi[r] % mod * fi[n - r] % mod
fa = [1] * (n + 1)
fi = [1] * (n + 1)
for i in range(1, n + 1):
    fa[i] = fa[i - 1] * i % mod
    fi[i] = pow(fa[i], mod - 2, mod)
def add(i, x):
    while i <= len(BIT):
        BIT[i] += x
        i += i & -i
def query(i):
    s = 0
    while i > 0:
        s += BIT[i]
        i -= i & -i
    return s
a = list(map(int, input().split()))
lis = sorted(list(set(a)))
l, r = 0, len(lis)
while r - l > 1:
    BIT = [0] * (2 * (n + 1) + 100)
    m = (l + r) // 2
    cum = [0]
    for i in range(n):
        cur = 1 if a[i] >= lis[m] else -1
        cum.append(cum[-1] + cur)
    cnt = 0
    for i in range(n + 1):
        cur = n + cum[i] + 5
        cnt += query(cur)
        add(cur, 1)
    if n * (n + 1) // 2 <= cnt * 2:
        l = m 
    else:
        r = m
print(lis[l])

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
ary=a.copy()
ary=sorted(list(set(ary)))
from bisect import bisect_left
aa=[bisect_left(ary,x) for x in a]
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        self.depth = n.bit_length()

    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 chk(x):
    c=[1 if ai<=x else -1 for ai in aa]
    cc=[0]
    tmp=0
    mi,ma=0,0
    for xx in c:
        tmp+=xx
        cc.append(tmp)
        mi=min(mi,tmp)
        ma=max(ma,tmp)
    
    
    bit=Bit(ma-mi+1)
    ret=0
    for xx in cc:
        xx-=mi
        xx+=1
        bit.add(xx,1)
        ret+=bit.sum(xx-1)
    return ret>(((n+1)*n)//2)//2

l,r=0,n
while r-l>1:
    x=(l+r)//2
    if chk(x):
        l,r=l,x
    else:
        l,r=x,r
print(ary[l] if chk(l) else ary[r])

Solution (Python):
import sys
input = sys.stdin.readline
from itertools import accumulate
n = int(input())
m = (n*(n+1)//2+1)//2
U = 2**20
A = tuple(map(int, input().split()))
def test(x):
  L = [0] + list(accumulate((-1)**(a<x) for a in A))
  B = [0]*(U+1)
  def add(i):
    while i<=U:
      B[i] += 1
      i += i & -i
  def acc(i):
    res = 0
    while i:
      res += B[i]
      i -= i & -i
    return res
  cnt = 0
  for l in L:
    cnt += acc(l+n+5)
    add(l+n+5)
  return cnt >= m
ok = 0
ng = 10**9+1
while ng - ok > 1:
  mid = (ng+ok)//2
  if test(mid):
    ok = mid
  else:
    ng = mid
print(ok)

Solution (Python):
def examA():
    N, i = LI()
    ans = N - i + 1
    print(ans)
    return

def examB():
    H, W = LI()
    A = [SI() for _ in range(H)]
    h = [[]for _ in range(H)]
    for i in range(W):
        flag = False
        for j in range(H):
            if A[j][i]=="
                flag = True
                break
        if flag:
            for j in range(H):
                h[j].append(A[j][i])
    
    ans = []
    for i,a in enumerate(h):
        if "
            ans.append(i)
    for v in ans:
        print("".join(map(str,h[v])))
    return

def examC():
    N, K = LI()
    X = LI()
    ans = inf
    for i in range(N-K+1):
        if X[i]<0 and X[i+K-1]>0:
            cur = (-X[i] + X[i+K-1]) + min(-X[i], X[i+K-1])
        else:
            cur = max(-X[i], X[i+K-1])
        ans = min(ans,cur)
    print(ans)
    return

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

        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
            return
    def inversion_number(n,A):
        bit = Bit(n+1)
        rep = 0
        for i, a in enumerate(A):
            bit.add(a, 1)
            rep += i + 1 - bit.sum(a)
        return rep
    N = I()
    A = LI()
    judge = (N*(N+1)//2 + 1)//2
    l = 0; r = max(A)+1
    while(r-l>1):
        
        now = (l+r)//2
        S = [0]*(N+1)
        cur = N*(N+1)//2
        for i in range(N):
            if A[i]>=now:
                S[i+1] += 1
            else:
                S[i+1] -= 1
                
        for i in range(1,N):
            S[i+1] += S[i]
            S[i] += N+1
        S[0] += N+1
        S[N] += N+1
        
        cur -= inversion_number(2*N+10,S)
        
        
        
        if cur>=judge:
            l = now
        else:
            r = now

    ans = l
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

"""

"""

Solution (Python):

def f(n, a):
    x = sorted(set(a))
    n_sub_half = (n * (n + 1)) // 2 // 2
    n1 = n * 2 + 1
    li = 0
    ri = len(x)
    while ri > li + 1:
        i = (li + ri) // 2
        xi = x[i]
        cnt = [0] * n1
        cs = 0
        cnt[cs] = 1
        judge = 0
        s = 0
        for ak in a:
            if ak >= xi:
                cs += 1
                s += cnt[cs] + 1
            else:
                cs -= 1
                s -= cnt[cs + 1] - 1
            cnt[cs] += 1
            judge += s
            if judge >= n_sub_half:
                li = i
                break
        else:
            ri = i
    return x[li]

n = int(input())
ar = [int(i) for i in input().strip().split(" ")]
print(f(n,ar))

Solution (Python):
from itertools import accumulate

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

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

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

N = int(input())
a = list(map(int, input().split()))
lb, ub = -1, 10**9
while ub - lb > 1:
  m = (lb + ub) // 2
  b = [0] * (N+1)
  for i in range(N):
    if a[i] <= m:
      b[i+1] = 1
  b = list(accumulate(b))
  bit_odd = BIT(2*N)
  bit_even = BIT(2*N)
  cnt = 0
  for i in range(N):
    x = N + b[i+1] - i//2 - 1
    y = N + b[i+1] - (i+1)//2 - 1
    if i % 2 == 0:
      bit_even.add(N + b[i] - i//2, 1)
      cnt += bit_even.sum(x) + bit_odd.sum(y)
    else:
      bit_odd.add(N + b[i] - i//2, 1)
      cnt += bit_even.sum(y) + bit_odd.sum(x)
  if cnt < N*(N+1)//4 + 1:
    lb = m
  else:
    ub = m
print(ub)

Solution (Python):
from itertools import accumulate
from math import *
import os, sys
from io import BytesIO
 
input = BytesIO(os.read(0, os.fstat(0).st_size)).readline
 
N = int(input())
A = list(map(int, input().split()))
 
 
class FenV:
    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 = FenV(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):
from itertools import accumulate
import sys
input = sys.stdin.readline

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

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

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

N = int(input())
a = list(map(int, input().split()))
lb, ub = -1, 10**9
while ub - lb > 1:
    m = (lb + ub) // 2
    b = [0] * (N+1)
    for i in range(N):
        if a[i] <= m:
            b[i+1] = 1
    b = list(accumulate(b))
    
    
    bit_odd = BIT(2*N)
    bit_even = BIT(2*N)
    cnt = 0
    for i in range(N):
        x = N + b[i+1] - i//2 - 1
        y = N + b[i+1] - (i+1)//2 - 1
        if i % 2 == 0:
            bit_even.add(N + b[i] - i//2, 1)
            cnt += bit_even.sum(x) + bit_odd.sum(y)
        else:
            bit_odd.add(N + b[i] - i//2, 1)
            cnt += bit_even.sum(y) + bit_odd.sum(x)
    if cnt < N*(N+1)//4 + 1:
        lb = m
    else:
        ub = m
print(ub)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
m = (n * (n + 1) // 2) // 2 + 1


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

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

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


def check(x):
    
    

    s = 0
    c = [0] * (n + 1)
    for i in range(n):
        c[i + 1] = c[i]
        if a[i] <= x:
            c[i + 1] += 1
    d = [2 * c[i] - i + n + 1 for i in range(n + 1)]
    d_max = max(d)
    bit = BIT1(d_max)

    cnt = 0
    for i in range(n + 1):
        cnt += bit.sum(d[i] - 1)
        bit.add(d[i], 1)
    return cnt >= m


lb = 0  
ub = max(a) + 1  
while ub - lb > 1:
    mid = (ub + lb) // 2
    if check(mid):
        ub = mid
    else:
        lb = mid

print(ub)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()

class BIT:

    """
    https://tjkendev.github.io/procon-library/python/range_query/bit.html
    Binary index treeの実装
    配列[a1, a2,...,an]に対して以下のクエリをO(logn)で行う:
        1. aiにxを加える
        2. 区間和 ai + a(i+1) + ... + aj の和を求める
    isom法を使えば、
        1. aiの値を取得する
        2. 区間[i, j]の全ての数にxを加算する
    もO(logN)で行うことができる
    """

    def __init__(self, n):
        """
        添字は1スタート
        """
        self.n = n
        self.data = [0] * (n + 1)
        self.el = [0] * (n + 1)

    def add(self, i, x):
        """
        i>0に対してaiにxを加算(x < 0でもOK)
        """
        if i <= 0 or self.n < i:
            print("i should be within 1 to n")
        else:
            self.el[i] += x
            while i <= self.n:
                self.data[i] += x
                i += i & -i

    def sum(self, i):
        """
        添字1からiまでの累積和を求める
        """
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    def get(self, i, j=None):
        """
        添字iからjまでの累積和を求める
        j=Noneの場合はaiの値を返す
        """
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i - 1)


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

    """
    決め打ち二分探索な匂いがする。
    ans <= Xとするとこれはmedian[l, r] <= XなるものがN * (N + 1) // 4個より多く存在することに同値。
    median[l, r] <= Xなるペア[l, r]の個数は以下の用にして求まる：

    １、所与の数列の各元に対して、それがX以下なら-1、Xより大なら+1に置き換える。
    ２、その数列の累積和をとり、先頭に0を追加。
    ３、この数列の転倒数(i < j s.t.A[i] > A[j])を数えると、その個数がmedian[l, r] <= Xなるものの個数になっている。

    転倒数を求めるには分割統治法かBITを使う方法があるが、前者はソート前の配列をコピーする必要があるので
    計算量的に好ましくない？よって後者で実装する。

    この時数列中の数は正であることと、BITの葉ノードは数列中の数のうち最大のものにすることが要求されるが
    今回の場合累積和をとった数列Bの要素は-N以上N以下なのでN + 1の下駄を履かせれば良い。（N <= 10^5なので初期化は十分間に合う）
    """

    left = 0
    right = 10**9
    while right - left > 1:
        
        mid = (left + right) // 2
        B = [0] * (N + 1)
        for i in range(1, N + 1):
            if A[i - 1] <= mid: B[i] = B[i - 1] - 1
            if A[i - 1] > mid: B[i] = B[i - 1] + 1

        
        tree = BIT(2 * N + 1) 
        cnt = 0
        for i in range(N + 1):
            tree.add(B[i] + N + 1, 1)
            cnt += tree.get(B[i] + N + 2, 2 * N + 1)
        

        if cnt > N * (N + 1) // 4: right = mid
        else: left = mid
    print(right)

if __name__ == "__main__":
    main()

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

class BIT():
    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
ok = 0
ng = 10**9+1

def inversion(a, bit):
    ans = 0
    for i, p in enumerate(b):
        bit.add(p, 1)
        ans += i+1 - bit.sum(p)
    return ans

while ng - ok > 1:
    m = ok + (ng-ok)//2
    b = [0]
    for i in range(n):
        if a[i] >= m:
            b.append(b[i]+1)
        else:
            b.append(b[i]-1)
    b = [i+100001 for i in b]
    bit = BIT(200005)
    inversion = 0
    for i, p in enumerate(b):
        bit.add(p, 1)
        inversion += i+1 - bit.sum(p)

    if inversion <= n*(n+1)//4:
        ok = m
    else:
        ng = m



print(ok)

Solution (Python):
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

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

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

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

def Binary_Search(A, B, N):
	
	left = 0
	right = N - 1
	ans = 0
	
	
	while left <= right:
		mid = (left + right) // 2
		var = B[mid]
		newlist = [None] * N
		
		for i in range(N):
			if A[i] >= var:
				newlist[i] = 1
			else:
				newlist[i] = -1
		
		newlistsum = [0]
		for i in range(N):
			newlistsum.append(newlistsum[-1] + newlist[i])
		cnt = 0
		bit = BIT(2 * N + 1)
		for i in range(N + 1):
			bit.add(newlistsum[i] + N, 1)
			cnt += bit.sum(newlistsum[i] + N) - 1

		if 4 * cnt >= N * (N + 1):
			ans = max(ans, B[mid])
			left = mid + 1
		else:
			right = mid - 1

	return ans


def main():
	N = int(input())
	A = getlist()
	B = sorted(A)
	ans = Binary_Search(A, B, N)
	print(ans)

if __name__ == '__main__':
	main()

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    a=list(map(int,input().split()))
    
    class BIT:
        def __init__(self,n):
            self.num=n
            self.dat=[0]*(self.num+1)
            self.depth=n.bit_length()
        
        def add(self,i,x):
            i+=1
            while i<=self.num:
                self.dat[i]+=x
                i+=i&-i
        
        def sum(self,i):
            i+=1
            s=0
            while i>0:
                s+=self.dat[i]
                i-=i&-i
            return s
        
        def lower_bound(self,x):
            sum_=0
            pos=0
            for i in range(self.depth,-1,-1):
                k=pos+(1<<i)
                if k<=self.num and sum_+self.dat[k]<x:
                    sum_+=self.dat[k]
                    pos+=1<<i
            return pos, sum_
    
    def nibutan(ok,ng):
        while abs(ok-ng) > 1:
            mid = (ok + ng) // 2
            if solve(mid):
                ok = mid
            else:
                ng = mid
        return ok
    
    def solve(mid):
        aa=[1 if x>=mid else -1 for x in a]
        b=BIT(N*2+1)
        c=0
        s=N
        b.add(s,1)
        for x in aa:
            s+=x
            c+=b.sum(s)
            b.add(s,1)
        return c>=-(-N*(N+1)//2//2)
    
    print(nibutan(1,10**9+1))

if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
a = 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):
        if not (0 <= i < self.size): raise ValueError("error!")
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

def search(x):
    l = [1 if i >= x else -1 for i in a]
    c = [n]
    for i in range(n):
        c.append(c[-1]+l[i])

    count = 0
    bit = Bit(2*n+1)
    for i in c:
        count += bit.sum(i+1)
        bit.add(i,1)
    
    return x,count

k = (n*(n+1)/2+1)//2
le = 0
ri = max(a)+1

while ri > le + 1:
    m = (ri+le)//2
    ans,count = search(m)

    if count >= k:
        le = m
    else:
        ri = m
print(le)

Solution (Python):

import sys
try:
    from typing import List
except ImportError:
    pass


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

    def add(self, n: int, v: int):
        while n < len(self.tr):
            self.tr[n] += v
            n += n & -n

    def cumsum(self, n: int):
        ans = 0
        while n > 0:
            ans += self.tr[n]
            n -= n & -n
        return ans


def solve(N: int, a: "List[int]"):

    def f(m):
        s = [0] * (N + 1)
        for i, ai in enumerate(a):
            s[i + 1] = s[i] + (-1 if ai < m else 1)
        ms = min(s)
        b = BIT(max(s) - ms + 1)
        t = 0
        for si in s:
            t += b.cumsum(si - ms + 1)
            b.add(si - ms + 1, 1)
        return t >= -(-(N * (N + 1) // 2) // 2)

    lb = 0
    rb = max(a) + 1
    while lb + 1 < rb:
        m = (lb + rb) // 2
        if f(m):
            lb = m
        else:
            rb = m

    print(lb)


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


if __name__ == '__main__':
    main()