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):

"""
タグ: 中央値、二分探索、転倒数
"""
class Bit:
    def __init__(self, n):
        self.n = n
        self.tree = [0]*(n+1)
        self.el = [0]*(n+1)
        self.depth = n.bit_length() - 1

    def sum(self, i):
        """ 区間[0,i) の総和を求める """
        s = 0
        i -= 1
        while i >= 0:
            s += self.tree[i]
            i = (i & (i + 1) )- 1
        return s

    def add(self, i, x):
        self.el[i] += x
        while i < self.n:
            self.tree[i] += x
            i |= i + 1

class BitSet2:
    """ 座標圧縮が必要な場合 """
    def __init__(self, data, A=[]):
        """ BitSetに入り得る値を先読みした物を data に格納 """
        self.data = sorted(list(set(data)))
        self.n = len(self.data)
        self.p = Bit(self.n + 1)
        self.size = 0
        self.flip = 0
        self.code = {}
        self.decode = {}
        for i, b in enumerate(self.data):
            self.code[b] = i
            self.decode[i] = b
        for a in A:
            self.add(a)

    def add(self,x):
        self.p.add(self.code[x], 1)
        self.size += 1
        self.flip += self.size - self.p.sum(self.code[x]+1)

    def remove(self,x):
        self.p.add(x, -1)
        self.size -= 1

    def flip_counter(self):
        return self.flip

def binary_search_int(ok, ng, test):
    """
    :param ok: solve(x) = True を必ず満たす点
    :param ng: solve(x) = False を必ず満たす点
    """
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if test(mid):
            ok = mid
        else:
            ng = mid
    return ok

def test(x):
    S = [0]
    for a in A:
        if a >= AS[x]:
            S.append(S[-1]+1)
        else:
            S.append(S[-1]-1)
    B = BitSet2(S,S)
    cnt = M - B.flip_counter()
    return cnt >= ceil(M/2)

import sys
from math import ceil
input = sys.stdin.readline

N = int(input())
M = N*(N+1)//2
A = list(map(int, input().split()))
AS = sorted(A)
print(AS[binary_search_int(0,N,test)])

Solution (Python):

"""
タグ: 中央値、二分探索、転倒数
"""
class Bit:
    def __init__(self, n):
        self.n = n
        self.tree = [0]*(n+1)
        self.el = [0]*(n+1)
        self.depth = n.bit_length() - 1

    def sum(self, i):
        """ 区間[0,i) の総和を求める """
        s = 0
        i -= 1
        while i >= 0:
            s += self.tree[i]
            i = (i & (i + 1) )- 1
        return s

    def add(self, i, x):
        self.el[i] += x
        while i < self.n:
            self.tree[i] += x
            i |= i + 1

class BitSet2:
    """ 座標圧縮が必要な場合 """
    def __init__(self, data, A=[]):
        """ BitSetに入り得る値を先読みした物を data に格納 """
        self.data = sorted(list(set(data)))
        self.n = len(self.data)
        self.p = Bit(self.n + 1)
        self.size = 0
        self.flip = 0
        self.code = {}
        self.decode = {}
        for i, b in enumerate(self.data):
            self.code[b] = i
            self.decode[i] = b
        for a in A:
            self.add(a)

    def add(self,x):
        self.p.add(self.code[x], 1)
        self.size += 1
        self.flip += self.size - self.p.sum(self.code[x]+1)

    def remove(self,x):
        self.p.add(x, -1)
        self.size -= 1

    def flip_counter(self):
        return self.flip

def binary_search_int(ok, ng, test):
    """
    :param ok: solve(x) = True を必ず満たす点
    :param ng: solve(x) = False を必ず満たす点
    """
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if test(mid):
            ok = mid
        else:
            ng = mid
    return ok

def test(x):
    S = [0]
    for a in A:
        if a >= x:
            S.append(S[-1]+1)
        else:
            S.append(S[-1]-1)
    B = BitSet2(S,S)
    cnt = M - B.flip_counter()
    return cnt >= ceil(M/2)

import sys
from math import ceil
input = sys.stdin.readline

N = int(input())
M = N*(N+1)//2
A = list(map(int, input().split()))
AS = sorted(A)
mi, ma = AS[0], AS[-1]
print(binary_search_int(mi,ma+1,test))

Solution (Python):
class BIT:
    def __init__(self,N):
        self.N=N
        self.bit=[0]*N
    def add(self,a,w):
        x=a
        while(x<self.N):
            self.bit[x]+=w
            x|=x+1
    def get(self,a):
        ret,x=0,a-1
        while(x>=0):
            ret+=self.bit[x]
            x=(x&(x+1))-1
        return ret
    def cum(self,l,r):
        return self.get(r)-self.get(l) 

def check(k):
    li=[]
    for i in range(N):
        li.append(1 if A[i]<=k else 0)

    c=[0]*(N+1)
    for i in range(N):
        c[i+1]=c[i]+li[i]
        
    d=[]
    for i in range(N+1):
        d.append(2*c[i]-i)
        
    S=sorted(set(d))
    dic={}
    for i,x in enumerate(S):
        dic[x]=i
    
    bit=BIT(N+1)
    res=0
    for i in range(N+1):
        bit.add(dic[d[i]],1)
        res+=bit.get(dic[d[i]])
    
    if res>M:
        return True
    else:
        return False

N=int(input())
A=list(map(int,input().split()))
M=N*(N+1)//4
l,r=-1,max(A)+1
while(r-l>1):
    k=(l+r)//2
    if check(k):
        r=k
    else:
        l=k

print(r)

Solution (Python):
n=int(input())
*a,=map(int, input().split())
def invr(x):
    if len(x)<=1:
        return x,0
    m=len(x)
    x1=x[:m//2]
    x2=x[m//2:]
    x11,res1=invr(x1)
    x22,res2=invr(x2)
    rx=[];res=res1+res2
    l=0;r=0
    while l<m//2 and r<m-(m//2):
        if x11[l]<=x22[r]:
            rx.append(x11[l])
            l+=1
        else:
            rx.append(x22[r])
            r+=1
            res+=m//2-l
    rx+=x11[l:]
    rx+=x22[r:]
    return rx,res

def f(m):
    a2=[(ai>=m)*2-1 for ai in a]
    a3=[0]
    for ai in a2:
        a3.append(a3[-1]+ai)
    _,r=invr(a3)
    return n*(n+1)//2-r>=((n+1)*n//2)//2



mx=max(a)+1;mn=min(a)
while mx-mn>1:
    md=(mx+mn)//2
    r=f(md)
    if r:
        mn=md
    else:
        mx=md
print(mn)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



n = int(input())
a = list(map(int, input().split()))
from collections import Counter
def sub(x):
    l = [1 if item>=x else -1 for item in a]
    count = [0] * (2*n+2)
    count[n] = 1
    i = n
    cumsum = 1
    ans = 0
    for item in l:
        i += item
        if item==1:
            cumsum += count[i]
        else:
            cumsum -= count[i+1]
        ans += cumsum
        count[i] += 1
        cumsum += 1
    return ans

l = 0
r = 10**9+1
tmp = (n+1)*n//2
thre = tmp//2 + tmp%2
while l<r-1:
    m = (l+r)//2
    if sub(m)>=thre:
        l = m
    else:
        r = m
print(l)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


def init(bit, values):
    for i,v in enumerate(values):
        update(bit,i,v)


def query(bit,i):
    res_sum = 0
    while i > 0:
        res_sum += bit[i]
        i -= i&(-i)
    return res_sum


def update(bit,i,x):
    while i <= len(bit)-1:
        bit[i] += x
        i += i&(-i)
    return


n = int(input())
a = list(map(int, input().split()))
from collections import Counter
def sub(x):
    cumsum = [None] * n
    cumsum[0] = 1 if a[0]>=x else -1
    for i in range(1,n):
        cumsum[i] = cumsum[i-1] + (1 if a[i]>=x else -1)

    
    
    bit = [0]*(2*n+2)
    update(bit, n+1, 1)
    ans = 0
    for v in cumsum:
        ans += query(bit, v+n+1)
        update(bit, n+v+1, 1)
    return ans

l = 0
r = 10**9+1
tmp = (n+1)*n//2
thre = tmp//2 + tmp%2
while l<r-1:
    m = (l+r)//2
    if sub(m)>=thre:
        l = m
    else:
        r = m
print(l)

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

def median(num):
    row=[0]*N
    for i in range(N):
        if A[i]>num:
            row[i]=1
        else:
            row[i]=-1
    m=0
    data=[0]
    for i in range(0,N):
        data.append(data[-1]+row[i])
        m=min(m,data[i+1])
    data=[data[i]-m+1 for i in range(N+1)]
    ans=0
    BIT=[0]*(N+2)
    n=N+1
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    for i in range(0,N+1):
        val=data[i]
        ans+=BIT_query(val)
        BIT_update(val,1)
    test=N*(N+1)//2-ans
    return test>=((N*(N+1)//2)//2+1)

start=0
end=10**9
while end-start>1:
    test=(end+start)//2
    if median(test):
        end=test
    else:
        start=test

if median(start):
    print(start)
else:
    print(end)

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))

class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0] * (n + 1)
    self.el = [0] * (n + 1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j = None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)
  def lowerbound(self, s):
    x = 0
    y = 0
    for i in range(self.n.bit_length(), -1, -1):
      k = x + (1 << i)
      if k <= self.n and (y + self.data[k] < s):
        y += self.data[k]
        x += 1 << i
    return x + 1

def check(x):
  b = [0] * N
  for i in range(N):
    if a[i] <= x: b[i] = -1
    else: b[i] = 1
  cs = [0] * (N + 1)
  for i in range(N): cs[i + 1] = cs[i] + b[i]
  mn = -min(cs) + 1
  fwk = BIT(N + 1)
  k = 0
  for i in range(N + 1):
    k += fwk.sum(cs[i] + mn)
    fwk.add(cs[i] + mn, 1)
  
  return k < N * (N + 1) // 4


ok = max(a)
ng = 0
while ok - ng > 1:
  m = (ok + ng) // 2
  if check(m): ok = m
  else: ng = m
print(ok)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
sortA=sorted(set(a))+[float('inf')]
def isOK(m):
  x=sortA[m]
  count=[0]*(2*n+1)
  count[n+1]=1
  i=n+1
  s=1
  res=0
  for b in a:
    if b>=x:
      i+=1
      s+=count[i]
    else:
      s-=count[i]
      i-=1
    res+=s
    count[i]+=1
    s+=1
  if res>=n*(n+1)//4:
    return False
  else:
    return True
l=0
r=len(sortA)-1
while r>l+1:
  mid=(r+l)//2
  if isOK(mid):
    r=mid
  else:
    l=mid
print(sortA[l])

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


class BIT():
    """一点加算、区間取得クエリをそれぞれO(logN)で答える
    add: i番目にvalを加える
    get_sum: 区間[l, r)の和を求める
    i, l, rは0-indexed
    """
    def __init__(self, n):
        self.n = 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, val):
        """i番目にvalを加える"""
        i = i + 1
        while i <= self.n:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)



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


def solve(val):
    val = a_sorted[val]
    ruiseki = [0] * (n + 1)
    for i, num in enumerate(a):
        if num >= val:
            ruiseki[i + 1] = ruiseki[i] + 1
        else:
            ruiseki[i + 1] = ruiseki[i] - 1
    b = sorted(enumerate(ruiseki), key = itemgetter(1))
    for i in range(n + 1):
        bit.bit[i] = 0
    res = 0
    for i, _ in b:
        bit.add(i, 1)
        res += bit.get_sum(0, i)
        if res >= cnt:
            return True
    return False


cnt = 0
for i in range(n):
    cnt += n - i
cnt = (cnt + 1) // 2

bit = BIT(n + 1)
ok = 0
ng = n
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid
print(a_sorted[ok])

Solution (Python):

def bitadd(a,w,bit): 
 
    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)
 
def bitsum(a,bit): 
 
    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret


def updiv(a,b):
    if a % b == 0:
        return a//b
    else:
        return a//b +1

def want(x):

    lis = []
    for i in a:
        if i >= x:
            lis.append(1)
        else:
            lis.append(-1)

    slis = [0]
    for i in lis:
        slis.append(slis[-1] + i)

    
    dic = {}
    nlis = []
    for i in slis:
        if i not in dic:
            dic[i] = None
            nlis.append(i)
    nlis.sort()
    for i in range(len(nlis)):
        dic[nlis[i]] = i+1

    
    
    ans = 0
    BIT = [0] * (len(nlis) + 1)

    for i in slis:
        j = dic[i]

        ans += bitsum(j,BIT)
        bitadd(j,1,BIT)
        
    
    return ans
    

N = int(input())

a = list(map(int,input().split()))

l = 1
r = max(a) + 1

while r-l != 1:

    m = (l+r) // 2

    mnum = want(m)

    if mnum >= updiv((N**2+N)//2,2):
        l = m
    else:
        r = m

print (l)

Solution (Python):
from itertools import accumulate

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

Bs = sorted(As)
M = N*(N+1)//2

def isOK(mid):
    Am = Bs[mid]
    Ss = [1 if A >= Am else -1 for A in As]
    Ss = list(accumulate([0]+Ss))

    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [0] * (numPow2+1)
        return data, numPow2
    def addValue(iA, A):
        iB = iA + 1
        while iB <= numPow2:
            data[iB] += A
            iB += iB & -iB
    def getSum(iA):
        iB = iA + 1
        ans = 0
        while iB > 0:
            ans += data[iB]
            iB -= iB & -iB
        return ans

    data, numPow2 = makeBIT(N+1)
    iSs = list(range(N+1))
    iSs.sort(key=lambda iS: Ss[iS])
    odrSs = [0]*(N+1)
    for odrS, iS in enumerate(iSs):
        odrSs[iS] = odrS

    num = 0
    for odrS in odrSs:
        num += getSum(odrS)
        addValue(odrS, 1)
    return num >= (M+1)//2


ng, ok = N, -1
while abs(ok-ng) > 1:
    mid = (ng+ok) // 2
    if isOK(mid):
        ok = mid
    else:
        ng = mid

print(Bs[ok])

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def add(i):
        while i < len(bit):
            bit[i] += 1
            i += i&-i
    def sum(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i&-i
        return res
    n = I()
    a = LI()
    f = list(set(a))
    f.sort()
    c = [bisect.bisect_left(f,i) for i in a]
    k = ((n*(n+1)) >> 1) >> 1
    l = 0
    r = len(f)
    while r-l > 1:
        m = (l+r) >> 1
        b = [2*(i < m)-1 for i in c]
        s = [0]
        for i in b:
            s.append(s[-1]+i)
        b = list(set([i for i in s]))
        b.sort()
        s = [bisect.bisect_left(b,i)+1 for i in s]
        bit = [0]*(max(s)+1)
        res = 0
        for i in s:
            res += sum(i)
            add(i+1)
        if res <= k:
            l = m
        else:
            r = m
    print(f[l])
    return


if __name__ == "__main__":
    solve()

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
from itertools import accumulate

def bsearch(target, min_i, max_i, func):
    
    if func(max_i) <= target:
        return max_i
    if target < func(min_i):
        return None
    index = (max_i + min_i)//2
    while True:
        if max_i - min_i <= 1:
            return min_i
        if func(index) <= target:
            index, min_i = (index + max_i)//2, index
            continue
        index, max_i = (index + min_i)//2, index

N, = map(int, input().split())
As = list(map(int, input().split()))
mna, mxa = min(As), max(As)

def tento(xs):
    bit = Bit(max(xs)+1)
    ans = 0
    for i, p in enumerate(xs):
        ans += bit.sum(p)
        bit.add(p, 1)
        
    
    return ans

def f(x):
    Bs = [0] + list(accumulate(map(lambda a: 1 if a>=x else -1, As)))
    mn = min(Bs)
    Bs = list(map(lambda x : x - mn + 1, Bs))
    return -tento(Bs)

M = (N*(N+1))//2
print(bsearch((-M//2) , mna, mxa, f))

Solution (Python):
from itertools import accumulate


class Bit:
    
    
    
    
    
    def __init__(self, a):
        if hasattr(a, "__iter__"):
            le = len(a)
            self.n = 1 << le.bit_length()  
            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):  
        values = self.values
        res = 0
        while i > 0:
            res += values[i]
            i -= i & -i
        return res

    def bisect_left(self, v):  
        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  
    
    
    for i, a in enumerate(A_sign_cum, 1):
        cnt += i - bit.sum(geta + a)
        
        bit.add(geta + a, 1)
    
    
    return N * (N+1) // 4 + 1 <= cnt


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

    
    
    
    
    
    
    

    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()

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):
class BIT(object):
    def __init__(self, n):
        self.n = 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.n:
            self.bit[i] += x
            i += i & (-i)


def main():
    n = int(input())
    *a, = map(int, input().split())
    small, large = 0, max(a)
    criteria = n * (n + 1) // 4

    while large - small > 1:
        mid = (small + large) // 2
        num = 0
        b = BIT(2 * n + 1)
        suma = 0
        b.add(suma + n + 1, 1)
        for aa in a:
            suma += 1 if aa <= mid else -1
            num += b.sum(suma + n)
            b.add(suma + n + 1, 1)

        if num > criteria:
            large = mid
        else:
            small = mid
    print(large)


main()

Solution (Python):
n = int(input())
a = [int(item) for item in input().split()]
a_sorted = sorted(a)

def can_be_midofmid(b):
    high_low_cum = [0] * (n + 1)
    for i, item in enumerate(a):
        if item >= b:
            high_low_cum[i+1] = 1
        else:
            high_low_cum[i+1] = -1
    for i in range(n):
        high_low_cum[i+1] += high_low_cum[i]
    bit_n = 1 << n.bit_length()
    bit = [0] * (bit_n+1)

    def bit_add(x, w):
        while x <= bit_n:
            bit[x] += w
            x += x & -x

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

    val = 0
    dic = dict(zip(sorted(high_low_cum), [item for item in range(len(high_low_cum))]))
    for i, item in enumerate(high_low_cum):
        val += bit_sum(dic[item] + 1)
        bit_add(dic[item] + 1, 1)
    return val  >= ((n+1) * n + 2)// 4  

l = -1; r = n
while r - l > 1:
    mid = (r + l) // 2
    if can_be_midofmid(a_sorted[mid]):
        l = mid
    else:
        r = mid
print(a_sorted[r-1])

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


class BinaryIndexedTree:
    """
        Parameters
        ----------
        array : list
            to construct BIT from
        f : func
            binary operation of the abelian group
        fi : func
            inverse mapping of f
            i.e. f(a, b) == c <-> fi(c, a) == b
        e : 
            identity element of the abelian group
        size : int
            limit for array size
    """

    def __init__(self, array, f, fi, e, size):
        self.f = f
        self.fi = fi
        self.e = e
        self.size = size
        self.n = len(array)
        self.dat = [e] * (size + 1)
        self.array = [e] * size
        

    def build(self, array_):
        for i, v in enumerate(array_):
            self.modify(i, v)

    def modify(self, p, v):
        """
        set value at position p (0-indexed)
        """
        self.add(p, self.fi(v, self.array[p]))
    
    def add(self, p, dv):
        """
        add value at position p (0-indexed)
        """
        fi, dat, f, size, array = self.fi, self.dat, self.f, self.size, self.array
        array[p] = f(array[p], dv)
        p += 1
        while p <= size:
            dat[p] = f(dat[p], dv)
            p += p & -p

    def query(self, l, r):
        """
        result on interval [l, r) (0-indexed)
        """
        return self.fi(self._query(r), self._query(l))

    def _query(self, p):
        dat, f, res = self.dat, self.f, self.e
        while p:
            res = f(res, dat[p])
            p -= p & -p
        return res


e = 0
size = 2 * N + 2
f = lambda a, b: a + b
fi = lambda c, a: c - a
offset = N


def check(x):
    cumsum = list(itertools.accumulate([0] + [1 if a <= x else -1 for a in A]))
    
    
    BIT = BinaryIndexedTree([e] * size, f=f, fi=fi, e=e, size=size)
    count = 0
    for c in cumsum:
        c += offset
        count += BIT._query(c + 1)
        BIT.add(c + 1, 1)
    return 2 * count > N * (N + 1) // 2


A_sorted = [0] + sorted(set(A)) + [10**10]
lb = 0
rb = len(A_sorted) - 1

while rb - lb > 1:
    mid = (rb + lb) // 2
    if check(A_sorted[mid]):
        rb = mid
    else:
        lb = mid
print(A_sorted[rb])

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


class SegmentTree():
    """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        e : 
            identity element of the monoid
        size : int
            limit for array size
    """

    def __init__(self, array, f, e, size):
        self.f = f
        self.e = e
        self.size = size
        self.n = n = len(array)
        self.dat = [e] * n + array + [e] * (2 * size - 2 * n)
        self.build()

    def build(self):
        dat, n, f = self.dat, self.n, self.f
        for i in range(n - 1, 0, -1):
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def modify(self, p, v):
        """
        set value at position p (0-indexed)
        """
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            dat[p >> 1] = f(dat[p], dat[p ^ 1])
            p >>= 1

    def query(self, l, r):
        """
        result on interval [l, r) (0-indexed)
        """
        f, e, n, dat = self.f, self.e, self.n, self.dat
        res = e
        l += n
        r += n
        while l < r:
            if l & 1:
                res = f(res, dat[l])
                l += 1
            if r & 1:
                r -= 1
                res = f(res, dat[r])
            l >>= 1
            r >>= 1
        return res


e = 0
size = 2 * N + 2
f = lambda a, b: a + b
offset = N


def check(x):
    cumsum = list(itertools.accumulate([0] + [1 if a <= x else -1 for a in A]))
    
    
    ST = SegmentTree([e] * size, f=f, e=e, size=size)
    count = 0
    for c in cumsum:
        c += offset
        count += ST.query(0, c + 1)
        ST.modify(c + 1, ST.query(c + 1, c + 2) + 1)
    return 2 * count > N * (N + 1) // 2


A_sorted = [0] + sorted(set(A)) + [10**10]
lb = 0
rb = len(A_sorted) - 1

while rb - lb > 1:
    mid = (rb + lb) // 2
    if check(A_sorted[mid]):
        rb = mid
    else:
        lb = mid
print(A_sorted[rb])

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


def check(x):
    class SegmentTree():
        """
            Parameters
            ----------
            array : list
                to construct segment tree from
            f : func
                binary operation of the monoid
            e : 
                identity element of the monoid
            size : int
                limit for array size
        """

        def __init__(self, array, f, e, size):
            self.f = f
            self.e = e
            self.size = size
            self.n = n = len(array)
            self.dat = [e] * n + array + [e] * (2 * size - 2 * n)
            self.build()

        def build(self):
            dat, n, f = self.dat, self.n, self.f
            for i in range(n - 1, 0, -1):
                dat[i] = f(dat[i << 1], dat[i << 1 | 1])

        def modify(self, p, v):
            """
            set value at position p (0-indexed)
            """
            f, n, dat = self.f, self.n, self.dat
            p += n
            dat[p] = v
            while p > 1:
                dat[p >> 1] = f(dat[p], dat[p ^ 1])
                p >>= 1

        def query(self, l, r):
            """
            result on interval [l, r) (0-indexed)
            """
            f, e, n, dat = self.f, self.e, self.n, self.dat
            res = e
            l += n
            r += n
            while l < r:
                if l & 1:
                    res = f(res, dat[l])
                    l += 1
                if r & 1:
                    r -= 1
                    res = f(res, dat[r])
                l >>= 1
                r >>= 1
            return res

    cumsum = list(itertools.accumulate([0] + [1 if a <= x else -1 for a in A]))
    
    
    e = 0
    size = 2 * N + 10
    ST = SegmentTree([e] * size, f=lambda x, y: x + y, e=e, size=size)
    count = 0
    for c in cumsum:
        c += N + 5
        count += ST.query(0, c + 1)
        ST.modify(c + 1, ST.query(c + 1, c + 2) + 1)
    return 2 * count > N * (N + 1) // 2


A_sorted = [0] + sorted(set(A)) + [10**10]
lb = 0
rb = len(A_sorted) - 1

while rb - lb > 1:
    mid = (rb + lb) // 2
    if check(A_sorted[mid]):
        rb = mid
    else:
        lb = mid
print(A_sorted[rb])

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


class BinaryIndexedTree:
    """
        Parameters
        ----------
        array : list
            to construct BIT from
        f : func
            binary operation of the abelian group
        fi : func
            inverse mapping of f
            i.e. f(a, b) == c <-> fi(c, a) == b
        e : 
            identity element of the abelian group
        size : int
            limit for array size
    """

    def __init__(self, array, f, fi, e, size):
        self.f = f
        self.fi = fi
        self.e = e
        self.size = size
        self.n = len(array)
        self.dat = [e] * (size + 1)
        self.array = [e] * size
        self.build(array)

    def build(self, array_):
        for i, v in enumerate(array_):
            self.modify(i, v)

    def modify(self, p, v):
        """
        set value at position p (0-indexed)
        """
        fi, dat, f, size, array = self.fi, self.dat, self.f, self.size, self.array
        dv = fi(v, array[p])
        array[p] = v
        p += 1
        while p <= size:
            dat[p] = f(dat[p], dv)
            p += p & -p

    def query(self, l, r):
        """
        result on interval [l, r) (0-indexed)
        """
        return self.fi(self._query(r), self._query(l))

    def _query(self, p):
        dat, f, res = self.dat, self.f, self.e
        while p:
            res = f(res, dat[p])
            p -= p & -p
        return res


e = 0
size = 2 * N + 2
f = lambda a, b: a + b
fi = lambda c, a: c - a
offset = N


def check(x):
    cumsum = list(itertools.accumulate([0] + [1 if a <= x else -1 for a in A]))
    
    
    BIT = BinaryIndexedTree([e] * size, f=f, fi=fi, e=e, size=size)
    count = 0
    for c in cumsum:
        c += offset
        count += BIT.query(0, c + 1)
        BIT.modify(c + 1, BIT.query(c + 1, c + 2) + 1)
    return 2 * count > N * (N + 1) // 2


A_sorted = [0] + sorted(set(A)) + [10**10]
lb = 0
rb = len(A_sorted) - 1

while rb - lb > 1:
    mid = (rb + lb) // 2
    if check(A_sorted[mid]):
        rb = mid
    else:
        lb = mid
print(A_sorted[rb])