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:
    '''
    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 bitsum(self, l, r=None): 
        if r is None:
            return self._bitsum(l)
        else:
            return self._bitsum(r) - self._bitsum(l)

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

n = int(input())
m = n * (n + 1) // 4
a = list(map(int, input().split()))
d = dict()
_a = sorted(set(a + [0]))
for i, x in enumerate(_a):
  d[x] = i
a = [d[x] for x in a]


def check(X):
  b = [0] + [(y>=X)*2 - 1 for y in a]
  for i in range(n):
    b[i+1] += b[i]
  c = min(b)
  b = [x-c for x in b] 
  bit = BIT(max(b) + 2)
  ans = 0
  for x in b:
    ans += bit.bitsum(x + 1)
    bit.bitadd(x, 1)
  return ans >= m

t = [len(_a), 0]
while t[0] - t[1] > 1:
  mid = (t[0] + t[1]) // 2
  t[check(mid)] = mid
print(_a[t[1]])

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

class BIT:
    
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    
    def add(self, i, x):
        i += 1
        
        while i<=self.n:
            self.bit[i] += x
            i += i&(-i)
    
    
    def acc(self, i):
        i += 1
        s = 0
        
        while i>0:
            s += self.bit[i]
            i -= i&(-i)
        
        return s
        
def compress(l):
    l = list(set(l))
    l.sort()
    idx = defaultdict(int)
    
    for i in range(len(l)):
        idx[l[i]] = i
    
    return idx

def judge(x):
    l = []
    
    for ai in a:
        if ai>=x:
            l.append(1)
        else:
            l.append(-1)
    
    acc = [0]*(N+1)
    
    for i in range(N):
        acc[i+1] = acc[i]+l[i]
    
    idx = compress(acc)
    bit = BIT(len(idx.keys()))
    cnt = 0
    
    for i in range(N+1):
        cnt += bit.acc(idx[acc[i]])
        bit.add(idx[acc[i]], 1)

    return cnt>=(N*(N+1)//2+1)//2
    
def binary_search():
    l, r = 0, max(a)
    
    while l<=r:
        m = (l+r)//2
        
        if judge(m):
            l = m+1
        else:
            r = m-1
    
    return r

N = int(input())
a = list(map(int, input().split()))
print(binary_search())

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):
def main():
    from itertools import accumulate as ac
    n = int(input())
    a = list(map(int, input().split()))

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

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

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

        
        def sum_range(self, i, j):
            return self.sum(j) - self.sum(i)

    def value(v):
        if n == 1:
            if v <= a[0]:
                return True
            else:
                return False
        b = [0]+list(ac([(i >= v)*2-1 for i in a]))
        bit = BIT(2*n+1)
        ans = 0
        bit.add(b[-1]+n, 1)
        for i in range(n-1, -1, -1):
            w = b[i]
            ans += bit.sum_range(w+n, 2*n+1)
            bit.add(w+n, 1)
        if ans >= (n*(n+1)//2)//2:
            return True
        else:
            return False

    def b_search(ok, ng, value):
        while abs(ok-ng) > 1:
            mid = (ok+ng)//2
            if value(mid):
                ok = mid
            else:
                ng = mid
        return ok

    print(b_search(0, 10**9+1, value))


main()

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):
from itertools import accumulate
from collections import defaultdict
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 jdg(x):
  b = [0 for i in range(n)]
  for i in range(n):
    if a[i] >= x:
      b[i] = 1
    else:
      b[i] = -1
  acc = [0]+list(accumulate(b))
  mn = min(acc)
  mx = max(acc)
  dif = mx-mn
  bit = Bit(dif+2)
  ret = 0
  for i in range(n+1):
    p = acc[i]-mn+1
    ret += bit.sum(p)
    bit.add(p,1)
  return ret
l = 0
r = max(a)+1
while l+1 < r:
  x = (l+r)//2
  if jdg(x) >= (n+1)*n//4:
    l = x
  else:
    r = x
print(l)

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

Solution (Python):
def main():
    n,*a=map(int,open(0).read().split())
    m=n*-~n//2+1>>1
    ng=max(a)+1
    ok=0
    while ng-ok>1:
        mid=ok+ng>>1
        b=[1]+[0]*n*2
        c=d=s=0
        for t in a:
            if t>=mid:
                c+=1
                d+=b[c]+1
            else:
                d-=b[c]-1
                c-=1
            b[c]+=1
            s+=d
        if s>=m:ok=mid
        else:ng=mid
    print(ok)
main()

Solution (Python):
def main():
    def add(i,x):
        while i<=size:
            tree[i]+=x
            i+=i&-i
    n,*a=map(int,open(0).read().split())
    size=n-~n
    m=n*-~n//2+1>>1
    ng=max(a)+1
    ok=0
    while ng-ok>1:
        mid=ok+ng>>1
        tree=[0]*-~size
        c=n+1
        s=0
        add(c,1)
        for t in a:
            c+=1if t>=mid else-1
            i=c
            while i:
                s+=tree[i]
                i-=i&-i
            add(c,1)
        if s>=m:ok=mid
        else:ng=mid
    print(ok)
main()

Solution (Python):
class BIT:
    def __init__(self,n):
        self.size=n
        self.tree=[0]*-~n
    def sum(self,i):
        s=0
        while i:
            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,*a=map(int,open(0).read().split())
m=n*-~n//2+1>>1
ng=max(a)+1
ok=0
while ng-ok>1:
    mid=(ok+ng)//2
    b=BIT(n-~n)
    c=n+1
    s=0
    b.add(c,1)
    for t in a:
        c+=1if t>=mid else-1
        s+=b.sum(c)
        b.add(c,1)
    if s>=m:ok=mid
    else:ng=mid
print(ok)

Solution (Python):

class imosBIT():
    def __init__(self, N):
        self.N = N
        self.bit = [0 for _ in range(self.N+1)]
    
    def __str__(self):
        ret = []
        for i in range(1, self.N+1):
            ret.append(self.__getitem__(i))
        return "[" + ", ".join([str(a) for a in ret]) + "]"

    def __getitem__(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


import sys
input = sys.stdin.readline

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

l = 0
r = max(A) + 1
while r-l > 1:
    x = (l+r)//2
    P = [0]
    for a in A:
        p = +1 if a >= x else -1
        P.append(P[-1]+p)
    score = 0
    bit = imosBIT(2*N+5)
    for p in P:
        p += N+1
        score += bit[p]
        bit.add(p, 1)
    
    if score >= (N*(N+1)//2+1)//2:
        l = x
    else:
        r = x

print(l)

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N = int(input())
aa = inpl()

def calc(x):
	aa_dush = [-1]*N
	for i in range(N):
		if aa[i] >= x:
			aa_dush[i] = 1
	

	S = [0] 
	tmp = 0
	MIN = MAX = 0
	for i in range(N):
		tmp += aa_dush[i]
		MIN = min(tmp,MIN)
		MAX = max(tmp,MAX)
		S.append(tmp)
	
	

	L = (MAX-MIN+1) 
	bit = [0]*(L+1) 
	ans = 0
	for S_i in S:
		S_i -= (MIN-1) 

		
		tmp = 0
		x = S_i
		while x > 0:
			tmp += bit[x]
			x -= x & -x
		ans += tmp

		
		x = S_i
		while x <= L:
			bit[x] += 1
			x += x & -x

	return ans 

border = ( (N+1)*N//2 +1 )//2
OK = 0
NG = 10**9+3

while NG - OK > 1:
	mid = (OK+NG)//2
	if calc(mid) >= border:
		OK = mid
	else:
		NG = mid

print(OK)

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()))
all_pattern = n * (n+1) // 2
check = all_pattern // 2 + bool(all_pattern % 2)
X = sorted(A)

left = 0
right = n

while left + 1 < right:
    idx = (left+right) // 2
    x = X[idx]
    up_or_down = [1 if num >= x else -1 for num in A]
    cumsum = [n]
    total = n
    for point in up_or_down:
        total += point
        cumsum.append(total)

    tree = Bit(2*n+1)
    pattern = 0
    for p in cumsum:
        pattern += tree.sum(p)
        tree.add(p, 1)

    if pattern >= check:
        left = idx
    else:
        right = idx

print(X[left])

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
NN = ((N + 1) * N // 2 + 1) // 2

def ok(x):
    B = [0] * (2 * N + 1)
    res, cum, cur = 0, 0, 0
    B[0] += 1
    for a in A:
        if a >= x:
            cum += 1
            cur += B[cum]+1
        else:
            cur -= B[cum]-1
            cum -= 1
        B[cum] += 1
        res += cur
    return res >= NN

B = sorted(set(A))
l = 0
r = len(B)
while r - l > 1:
    m = (l + r) // 2
    if ok(B[m]):
        l = m
    else:
        r = m
print(B[l])

Solution (Python):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


class BinaryIndexedTree:
    
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0] * size
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        [0, i) の合計
        :param int i:
        """
        ret = 0
        while i > 0:
            ret += self._bit[i - 1]
            i -= i & -i
        return ret

    def __len__(self):
        return self._size


def median(A):
    return list(sorted(A))[len(A) // 2]


def test(A):
    N = len(A)
    M = []
    for l in range(N):
        for r in range(l + 1, N + 1):
            M.append(median(A[l:r]))
    print(median(M))


def less_than(k):
    arr = [0] * (N + 1)
    for i, b in enumerate(B):
        arr[i + 1] = 1 if b >= k else -1
    cum = cumsum(arr)
    base = min(cum)
    for i in range(len(cum)):
        cum[i] -= base

    
    
    
    bit = BinaryIndexedTree(size=max(cum) + 1)
    count = 0
    for i, c in enumerate(cum):
        count += i - bit.sum(c + 1)
        bit.add(c, 1)

        
        
        if count > (N + 1) * N // 2 / 2:
            return True
    return False


def compress(li, origin=0):
    """
    座圧
    :param li:
    :param int origin:
    :rtype: list of int
    """
    *ret, = map({v: i + origin for i, v in enumerate(sorted(set(li)))}.__getitem__, li)
    return ret


def argsort(li, key=None, reverse=False):
    return [i for _, i in sorted(
        [(a, i) for i, a in enumerate(li)], key=(lambda t: key(t[0])) if key else None, reverse=reverse
    )]


def cumsum(it):
    """
    累積和
    :param collections.Iterable it:
    :return:
    """
    cs = 0
    ret = []
    for v in it:
        cs += v
        ret.append(cs)
    return ret


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))


indices = argsort(A)


B = compress(A)

lo = 0
hi = N
while abs(lo - hi) > 1:
    mid = (lo + hi) // 2
    if less_than(B[indices[mid]]):
        hi = mid
    else:
        lo = mid
print(A[indices[lo]])

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

class BIT:
    
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        self.p = 2**(n.bit_length() - 1)
        self.dep = n.bit_length()
    def get(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 bl(self, v):
        if v <= 0:
            return -1
        s = 0
        k = self.p
        for _ in range(self.dep):
            if s + k <= self.size and self.tree[s+k] < v:
                s += k
                v -= self.tree[s+k]
            k //= 2
        return s + 1

def compress(L):
    L2 = list(set(L))
    L2.sort()
    C = {v : k for k, v in enumerate(L2)}
    return L2, C

N = int(readline())
A = list(map(int, readline().split()))
A2, C = compress(A)
A = [C[a] for a in A]
ok = 0
ng = max(A)+1
T = BIT(ng)
ma = min(A)+1
while abs(ok-ng) > 1:
    med = (ok+ng)//2
    B = [1 if a >= med else -1 for a in A]
    for i in range(1, N):
        B[i] += B[i-1]
    
    
    mb = -min(0, min(B))+1
    T = BIT(max(B)+mb)
    T.add(mb, 1)
    res = 0
    for b in B:
        res += T.get(mb+b)
        T.add(mb+b, 1)
    if res >= N*(N+1)//4:
        ok = med
    else:
        ng = med
print(A2[ok])

Solution (Python):
class BIT:
    def __init__(self, n):
        self.N = n
        self.n = 1<<n.bit_length()
        self.data = [0] * (self.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):
        while i <= self.n:
            self.data[i] += x
            i += i & -i
N = int(input())
A = list(map(int, input().split()))
N0 = N*(N+1)//2
def C(x):
    B = BIT(N*2+1)
    s = [0]*(N+1)
    for i in range(N):
        a = A[i]
        s[i] = 1 if x<a else -1
        s[i]+=s[i-1]
    res = 0
    for i in range(-1, N):
        res+=B.sum(s[i]+N+1)
        B.add(s[i]+N+1, 1)
    return res<N0//2
ok = max(A)
ng = min(A)-1
while abs(ok-ng)>1:
    mid = (ok+ng)//2
    if C(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Solution (Python):
import sys

def bit_add(iii,x):
    while iii<len(bit):
        bit[iii]+=x
        iii+=iii&(-iii)
def bit_sum(jjj):
    s=0
    while jjj>0:
        s+=bit[jjj]
        jjj-=jjj&(-jjj)
    return s

n=int(input())
a=list(map(int,input().split()))
num=n*(n+1)//2
high=max(a)
low=min(a)
while high-low>1:
    mid=(high+low)//2
    ans=0
    b=[]
    for i in range(n):
        if a[i]>=mid:
            b.append(1)
        else:
            b.append(-1)
    for i in range(1,n):
        b[i]+=b[i-1]
    for i in range(n):
        b[i]+=n
    bit=[0]*(2*n+3)
    bit_add(n,1)
    for i in range(n):
        ans+=bit_sum(b[i])
        bit_add(b[i],1)
    if num%2==1:
        if ans>=num//2+1:
            low=mid
        else:
            high=mid
    else:
        if ans>=num//2:
            low=mid
        else:
            high=mid

            
            
if not high in a:
    print(low)
    sys.exit()
else:
    mid=high
    ans=0
    b=[]
    for i in range(n):
        if a[i]>=mid:
            b.append(1)
        else:
            b.append(-1)
    for i in range(1,n):
        b[i]+=b[i-1]
    for i in range(n):
        b[i]+=n
    bit=[0]*(2*n+3)
    bit_add(n,1)
    for i in range(n):
        ans+=bit_sum(b[i])
        bit_add(b[i],1)
    if num%2==1:
        if ans>=num//2+1:
            print(high)
        else:
            print(low)
    else:
        if ans>=num//2:
            print(high)
        else:
            print(low)

Solution (Python):
def main():
    N, *A = map(int, open(0).read().split())
 
    B = sorted(A)
    l, r = 0, N
    m, c = N // 2, N * (N + 1) // 2
 
    def check(x):
        b, r, y = N, 0, 0
        D = [0] * (2 * N + 1)
        for a in A:
            D[b] += 1
            if a < x:
                r += D[b]
                b += 1
            else:
                b -= 1
                r -= D[b]
            y += r
        return y
 
    while True:
        if check(B[m]) <= c // 2:
            if m == N - 1 or check(B[m + 1]) > c // 2:
                break
            else:
                l, m = m, (m + r) // 2
        else:
            m, r = (m + l) // 2, m + 1
 
    print(B[m])
 
 
if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class BIT(object):
    def __init__(self,A,dot=lambda x,y:x+y,e=0,inv=None):
        n=len(A)
        self.__n=n
        self.__dot=dot
        self.__e=e
        self.__inv=inv
        self.__node=['$']+A 
        for i in range(1,n+1):
            j=i+(i&-i)
            if(j<=n): self.__node[j]=dot(self.__node[i],self.__node[j])

    def add(self,i,w=1):
        i+=1
        while(i<=self.__n):
            self.__node[i]=self.__dot(self.__node[i],w)
            i+=i&-i

    def sum(self,i):
        res=self.__e
        while(i>0):
            res=self.__dot(res,self.__node[i])
            i-=i&-i
        return res

def bisection(l,r,f,left=True,discrete=True):
    eps=1 if discrete else 10**-12
    if((not left)^f(r)): return r if left else r+1
    elif(left^f(l)): return l-1 if left else l
    while(r-l>eps):
        h=(l+r)//2 if discrete else (l+r)/2
        if((not left)^f(h)): l=h
        else: r=h
    return (l+r)/2 if not discrete else l if left else r

def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    M=max(A)

    def check(x):
        B=[1 if(a>=x) else -1 for a in A]
        S=[0]*(n+1)
        for i in range(n):
            S[i+1]=S[i]+B[i]

        D={d:i for i,d in enumerate(sorted(set(S)))}
        for i in range(n+1):
            S[i]=D[S[i]]

        cnt=0
        bit=BIT([0]*(n+1))
        for i in range(n+1):
            cnt+=bit.sum(S[i]+1)
            bit.add(S[i])

        return cnt*2>=n*(n+1)//2

    print(bisection(0,M,check))
resolve()

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 18
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


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

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

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



n = I()
A = LI()



def D(L):
    n = len(L)
    bit = BIT(2 * n + 1)
    ans = 0
    for i in range(n - 1, -1, -1):
        bit.add(L[i] + n, 1)
        ans += bit.sum(L[i] + n - 1)
    return ans



ALL = (n + 1) * n // 2
A2 = sorted(A)

ng, ok = n, 0
while ng > ok + 1:
    mid = (ok + ng) // 2
    L = [0] + list(accumulate([1 if i >= A2[mid] else -1 for i in A]))
    if D(L) >= ALL // 2 + 1:
        ng = mid
    else:
        ok = mid


print(A2[ok])

Solution (Python):



import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

n = int(input())
a = [int(i) for i in readline().split()]

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

from collections import Counter
def isOK(x): 
    c = [1 if i >= x else -1 for i in a]
    res = Counter([0])
    now = 0
    less = 1
    ans = 0
    for i in range(n):
        if c[i] > 0:
            less += res[now+1]
        else:
            less -= res[now]
        now += c[i]
        ans += less
        less += 1
        res[now] += 1
    return ans >= (n*(n+1)//2+1)//2      


ans = binarysearch(0,10**9+1,isOK)
print(ans)

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

def chk(k):
    s = 0
    c = 0
    BIT=[0]*(2**NN+1)
    def add(i, x=1):
        i += 1 << NN - 1
        while i <= 2**NN:
            BIT[i] += x
            i += i & (-i)

    def getsum(i):
        ret = 0
        i += 1 << NN - 1
        while i != 0:
            ret += BIT[i]
            i -= i&(-i)
        return ret
    add(0)
    for i in range(N):
        if A[i] >= k:
            s += 1
        else:
            s -= 1
        c += getsum(s)
        add(s)
    if 4 * c >= N * (N+1):
        return 1
    return 0

l, r = 0, 1<<30
while r - l > 1:
    m = (l+r) // 2
    if chk(m):
        l = m
    else:
        r = m
print(l)

Solution (Python):
from itertools import accumulate

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

    def add(self, i, v):
        while i <= self.n:
            self.data[i-1] += v
            i += i & -i

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

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

def check(m):
    b = [[-1,1][i>=m] for i in a]
    bit = BIT_RSQ(2*n+1)
    s = [0] + list(accumulate(b))
    res = 0
    for i in range(n):
        bit.add(s[i]+n+1, 1)
        res += bit.sum(s[i+1]+n+1)
    return res >= (n*(n+1)//2+1)//2

left = 0
right = 10**9+1
while right-left > 1:
    mid = (right+left)//2
    if check(mid):
        left = mid
    else:
        right = mid
print(left)

Solution (Python):
from itertools import combinations
from math import ceil
N = int(input())
A = list(map(int, input().split()))
M = ceil(N*(N+1)/4)

class FenwickTree(object):
    def __init__(self, n):
        self._bit = [0] * (n+1)
        self.n = n+1
    
    def add(self, i, a):
        i += 1
        while i < self.n:
            self._bit[i] += a
            i += i & -i
    
    def sum(self, i):
        i += 1
        ret = 0
        while i > 0:
            ret += self._bit[i]
            i -= i & -i
        return ret

lo, hi = 0, max(A)+1
while lo < hi-1:
    mid = (lo+hi)//2
    B = [1 if a >= mid else -1 for a in A]
    C = []
    C.append(0)
    for b in B:
        C.append(C[-1]+b)
    cmin = min(C)
    for i in range(N+1):
        C[i] -= cmin  
    cmax = max(C)+1
    fw = FenwickTree(cmax)
    cnt = 0
    for i in range(N+1):
        cnt += fw.sum(C[i])
        fw.add(C[i], 1)

    if cnt >= M:
        lo = mid
    else:
        hi = mid

print(lo)

Solution (Python):
N = int(input())
a = [int(i) for i in input().split()]

half = ((N * (N + 1) // 2) + 1) // 2

class BinaryIndexedTree() :
    def __init__(self, N) :
        self.N = 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.N :
            self.tree[i] += x
            i += i & -i

def check(x) :
    b = [0] + [1 if a[i] >= x else -1 for i in range(N)]
    for i in range(1, N + 1) :
        b[i] += b[i-1]
    BIT = BinaryIndexedTree(2*N+2)
    
    ret = 0
    for i in range(N+1) :
        ret += BIT.sum(N+1+b[i])
        BIT.add(N+1+b[i], 1)
    
    return ret >= half
    
aa = sorted(a)
ok = 0
ng = N
while ng - ok > 1 :
    mid = (ok + ng) // 2
    if check(aa[mid]) :
        ok = mid
    else :
        ng = mid

print(aa[ok])

Solution (Python):

import sys
from itertools import accumulate
INF = float("inf")


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 inversion(a):
    "転倒していない組(l, r)の個数を求める"
    d = {av: i+1 for i, av in enumerate(sorted(a))}
    b = Bit(len(a))
    ans = 0
    for i, av in enumerate(a):
        ans += b.sum(d[av])
        b.add(d[av], 1)
    return ans


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

    def isOK(y):
        acc = (1 if aa >= y else -1 for aa in a)
        acc = tuple([0]) + tuple(accumulate(acc))
        invs = inversion(acc)
        if acc[0] == -1:
            invs -= 1
        return invs < (N*(N+1))//4

    def binary_search(x):

        ng = -1
        ok = len(x)+1

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

    ng, ok = binary_search(range(max(a)))
    print(ng)
    return


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

Solution (Python):
def mergecount(A):
    cnt = 0
    n = len(A)
    if n>1:
        A1 = A[:n>>1]
        A2 = A[n>>1:]
        cnt += mergecount(A1)
        cnt += mergecount(A2)
        i1 = 0
        i2 = 0
        for i in range(n):
            if i2 == len(A2):
                A[i] = A1[i1]
                i1 += 1
            elif i1 == len(A1):
                A[i] = A2[i2]
                i2 += 1
            elif A1[i1] <= A2[i2]:
                A[i] = A1[i1]
                i1 += 1
            else:
                A[i] = A2[i2]
                i2 += 1
                cnt += n//2 - i1
    return cnt
 
 
n = int(input())
l = [int(_) for _ in input().split()]
p = (n*n+n)/2
q = 0
if p%2 == 0:
    q = p//2
else:
    q = p//2 + 1
l_set = list(set(l))
l_sorted = sorted(l_set)
ans = 0
l_t = [0 for _ in range(n)]
s = [0 for _ in range(n+1)]
 
low = 0
high = len(l_sorted) - 1
 
 
while low <= high:
    mid = (low + high) // 2
    m = l_sorted[mid]
    for j in range(n):
        if l[j] < m:
            l_t[j] = -1
        else:
            l_t[j] = 1
    for k in range(n):
        s[k+1] = s[k] + l_t[k]
 
    x = mergecount(s)
    if p-x >= q:
        low = mid+1
        ans = max(m,ans)
    else:
        high = mid-1
print(ans)