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):
import math
n = int(input())
a = list(map(int, input().split()))

class BIT:
    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)
            
a_sorted = sorted(list(set(a)))
left, right = 0, len(a_sorted) 
while right-left > 1: 
    mid = (left+right)//2 
    num = 0 
    bit = BIT(2*n+1) 
    sum_ = 0 
    bit.add(sum_+n, 1)
    for i in range(n): 
        sum_ += 1 if a[i] >= a_sorted[mid] else -1 
        num += bit.sum(sum_+n) 
        bit.add(sum_+n, 1) 
    

    
    if num >= math.ceil(n*(n+1)//4):
        left = mid
    else:
        right = mid
print(a_sorted[left])

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

class BIT:
    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)
            
left, right = 0, 10**9
geta = n+1
while right-left > 1:
    mid = (left+right)//2
    num = 0
    bit = BIT(2*n+1)
    sum_ = 0
    bit.add(sum_+geta, 1)
    for i in range(n):
        val = 1 if a[i] <= mid else -1
        sum_ += val
        num += bit.sum(sum_+geta-1)
        bit.add(sum_+geta, 1)

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

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

a_sorted = sorted(set(a))+[10**18]
left, right = 0, len(a_sorted)-1

while right-left > 1:
    mid = (left+right)//2
    x = a_sorted[mid]

    count = [0]*(2*n+1)
    count[n+1] = 1
    i, accum, res = n+1, 1, 0

    for aa in a:
        if aa >= x:
            i += 1
            accum += count[i]
        else:
            accum -= count[i]
            i -= 1

        res += accum
        count[i] += 1
        accum += 1

    if res >= n*(n+1)//4:
        left = mid
    else:
        right = mid

print(a_sorted[left])

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

class BIT():
	def __init__(self, size):
		self.table = [0 for _ in range(size+2)]
		self.size = size

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

	def b_add(self, i, x):
		while i <= self.size:
			self.table[i] += x
			i += (i & -i)
		return

fr, ba = min(a), max(a)+1

while ba - fr > 1:
	mi = (fr+ba) // 2
	bit = BIT(n+1)
	res = 0
	inv = [0]
	min_tmp = 0
	
	for j in range(n):
		if a[j] >= mi:
			inv.append(inv[-1]+1)
		else:
			inv.append(inv[-1]-1)
			min_tmp = min(min_tmp, inv[-1])

	for j in range(n+1):
		res += bit.b_sum(inv[j] - min_tmp + 1)
		bit.b_add(inv[j] - min_tmp + 1, 1)

	if res >= (n * (n+1) / 4):
		fr = mi
	else:
		ba = mi

print(fr)

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

from itertools import accumulate

class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
        
    def node_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 reset(self):
        self.tree = [0] * (self.size + 1)
        
        
n = ni()
a = list(li())

t = n*(n+1) // 4
alt = sorted(set(a))

l,r = 0, len(alt) - 1
bitree = BIT(n*2)

while l <= r:
    m = (l+r) // 2
    am = alt[m]
    acc = accumulate(1 if ai-am >= 0 else -1 for ai in a)
    bitree.add(n,1)
    right_order = 0
    
    for p in acc:
        p += n
        right_order += bitree.node_sum(p)
        bitree.add(p, 1)
        
    if right_order >= t:
        l = m+1
    else:
        r = m-1
        
    bitree.reset()
    
print(alt[r])

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

def add(B,a,n):
    x = a
    while x<=n:
        B[x]+=1
        x+=x&(-x)
        
def sums(B,a):
    x=a
    S=0
    while x!=0:
        S+=B[x]
        x-=x&(-x)
    return S
  
  
  
def invnumber(n,A):
  B=[0]*(n*2+1)
  invs=0
  for i in range(n):
      s=A[i]+n
      invs+=sums(B,s)
      add(B,s,n*2)
  return n*(n-1)//2-invs
  
def Check(x):
  S=[0]
  for i in range(N):
    if A[i]>sorted_A[x]:
      S.append(S[-1]+1)
    else:
      S.append(S[-1]-1)
  return invnumber(N+1,S)
      
l,r=0,N-1
while l<r:
  m=(l+r)//2
  if Check(m)>N*(N+1)//4:
    r=m
  else:
    l=m+1
print(sorted_A[l])

Solution (Python):
class Fenwick:
    def __init__(self, size):
        self.arr = [0]*size
    
    def update(self, i, val):
        while i < len(self.arr): self.arr[i] += val; i |= i+1
    
    def getsum(self, i):
        res = 0
        while i >= 0: res+= self.arr[i]; i = (i&(i+1))-1
        return res

def paramin(F, l, r):
    while l <= r:
        mid = (l+r)//2
        if F(mid): ans, r = mid, mid-1
        else: l = mid+1
    return ans

from itertools import accumulate
def medleq(i):
    x = vals[i]
    M = [(y<=x)*2-1 for y in L]
    MA = list(accumulate(M))
    cnt = sum(y>0 for y in MA)
    F = Fenwick(2*n+3)
    for y in MA:
        c = y+n+1
        cnt+= F.getsum(c-1)
        F.update(c, 1)
    return cnt >= target

n = int(input())
L = list(map(int,input().split()))
tot = n + n*(n-1)//2
target = tot//2 + 1
vals = sorted(set(L))
print(vals[paramin(medleq, 0, len(vals)-1)])

Solution (Python):
class Fenwick:
    def __init__(self, size):
        self.arr = [0]*size
    
    def update(self, i, val):
        while i < len(self.arr): self.arr[i] += val; i |= i+1
    
    def getsum(self, i):
        res = 0
        while i >= 0: res+= self.arr[i]; i = (i&(i+1))-1
        return res

def paramin(F, l, r):
    while l <= r:
        mid = (l+r)//2
        if F(mid): ans, r = mid, mid-1
        else: l = mid+1
    return ans

from itertools import accumulate
def medleq(x):
    M = [(y<=x)*2-1 for y in L]
    MA = list(accumulate(M))
    cnt = sum(y>0 for y in MA)
    F = Fenwick(2*n+3)
    for y in MA:
        c = y+n+1
        cnt+= F.getsum(c-1)
        F.update(c, 1)
    return cnt >= target

n = int(input())
L = list(map(int,input().split()))
tot = n + n*(n-1)//2
target = tot//2 + 1
print(paramin(medleq, min(L), max(L)))

Solution (Python):


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

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


a_sorted = sorted(a_list)

left = 0
right = N
mid = N // 2
C = N*(N+1) // 2

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

Solution (Python):
class BIT():
    def __init__(self,number):
        self.n=number
        self.list=[0]*(number+1)
        
    def add(self,i,x):
        while i<=self.n:
            self.list[i]+=x
            i+=i&-i
            
    def search(self,i):
        s=0
        while i>0:
            s+=self.list[i]
            i-=i&-i
        return s
    
    def suma(self,i,j):
        return self.search(j)-self.search(i-1)
N=int(input())
A=[int(i) for i in input().split()]
if ((N*(N+1))//2)%2==1:
    a=((N*(N+1))//2)//2+1
else:
    a=((N*(N+1))//2)//2

def f(s):
    X=[1 if a>=s else -1 for a in A]
    p=[0]*(N+1)
    ma=0
    mi=0
    for i in range(1,N+1):
        p[i]=p[i-1]+X[i-1]
        ma=max(p[i],ma)
        mi=min(p[i],mi)
    tree=BIT(ma-mi+1)
    num=0
    for i in range(1,N+2):
        num+=tree.search(p[i-1]-mi+1)
        tree.add(p[i-1]-mi+1,1)
    if num>=a:
        return True
    else:
        return False
x=10**9+1
y=-1
while x-y>1:
    mid=(x+y)//2
    if f(mid):
        y=mid
    else:
        x=mid
print(y)

Solution (Python):
class BIT():
    def __init__(self,number):
        self.n=number
        self.list=[0]*(number+1)
        
    def add(self,i,x):
        while i<=self.n:
            self.list[i]+=x
            i+=i&-i
            
    def search(self,i):
        s=0
        while i>0:
            s+=self.list[i]
            i-=i&-i
        return s
    
    def suma(self,i,j):
        return self.search(j)-self.search(i-1)
N=int(input())
A=[int(i) for i in input().split()]
if ((N*(N+1))//2)%2==1:
    a=((N*(N+1))//2)//2+1
else:
    a=((N*(N+1))//2)//2

def f(s):
    X=[1 if a>=s else -1 for a in A]
    p=[0]*(N+1)
    for i in range(1,N+1):
        p[i]=p[i-1]+X[i-1]
    tree=BIT(2*N+1)
    num=0
    for i in range(1,N+2):
        num+=tree.search(p[i-1]+N+1)
        tree.add(p[i-1]+N+1,1)
    if num>=a:
        return True
    else:
        return False
x=10**9+1
y=-1
while x-y>1:
    mid=(x+y)//2
    if f(mid):
        y=mid
    else:
        x=mid
print(y)

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


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

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

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

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


BIT = BinaryIndexedTree(2 * N + 1)  
target = (N * (N+1) // 2 + 1) // 2


l, r = -1, 10**9+1

while r - l > 1:
    X = (r + l) // 2
    Binary = [(1 if a > X else -1) for a in A]
    Binary = list(accumulate(Binary))

    BIT.reset()

    inversion = 0

    for j in range(N):
        inversion += BIT.sum(Binary[j] + N + 1) + (Binary[j] >= 0)
        BIT.add(Binary[j] + N + 1, 1)

    if inversion >= target:
        l = X
    else:
        r = X

print(r)

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


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

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

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

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


BIT = BinaryIndexedTree(2 * N + 1)  
target = (N * (N+1)) // 4


l, r = -1, 10**9+1
if N == 1:
    print(A[0])
    exit()
while r - l > 1:
    X = (r + l) // 2
    Binary = [(1 if a > X else -1) for a in A]
    Binary = list(accumulate(Binary))

    BIT.reset()

    inversion = 0

    for j in range(N):
        inversion += BIT.sum(Binary[j] + N + 1) + (Binary[j] >= 0)
        BIT.add(Binary[j] + N + 1, 1)

    
    if inversion >= target:
        l = X
    else:
        r = X


print(r)

Solution (Python):
import sys
class BIT:
    def __init__(self, node_size):
        self._node = node_size+1
        self.bit = [0]*self._node

    def add(self, index, add_val):
        while index < self._node:
            self.bit[index] += add_val
            index += index & -index

    def sum(self, index):
        res = 0
        while index > 0:
            res += self.bit[index]
            index -= index & -index
        return res
def cheak(x):
  c = [0] * n
  for i in range(n):
    if a[i] >= x:
      c[i] = 1
    else:
      c[i] = -1
  ru = [0] * (n+1)
  for i in range(1,n+1):
    ru[i] = c[i-1] + ru[i-1]
  ans = 0
  bit = BIT(n+2)
  MIN = min(ru)
  for i in range(len(ru)):
    ans += i - bit.sum(ru[i]-MIN+1)
    bit.add(ru[i]-MIN+1, 1)
  if ans <= n*(n+1)//4:
    return 1
  else:
    return 0
n = int(input())
a = list(map(int, sys.stdin.readline().split()))
b = sorted(a)
dai = n-1
syo = 0
while True:
  if dai-syo <= 1:
    break
  kon = b[(dai+syo)//2]
  d = cheak(kon)
  if d == 1:
    syo = (dai+syo)//2
  else:
    dai = (dai+syo)//2
if cheak(b[dai]) == 1:
  print(b[dai])
else:
  print(b[syo])

Solution (Python):
def d_median_of_medians(N, A):
    class BIT(object):
        def __init__(self, n):
            self.size = n
            self.tree = [0] * (self.size + 1)

        def __str__(self):
            return '[{}]'.format(', '.join(map(str, self.tree)))

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

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

    def pair(x):
        a_prime = [-1] * N
        for k in range(N):
            if A[k] >= x:
                a_prime[k] = 1  

        s = [0]
        min_s = 0
        max_s = 0
        tmp = 0
        
        for a in a_prime:
            tmp += a
            min_s = min(min_s, tmp)
            max_s = max(max_s, tmp)
            s.append(tmp)

        bit_size = max_s - min_s + 1  
        bit = BIT(bit_size)
        ans = 0
        for sk in s:
            sk -= (min_s - 1)  
            ans += bit.sum(sk)
            bit.add(sk, 1)
        return ans

    
    border_median = (N * (N + 1) // 2 + 1) // 2
    ok = 0
    ng = 10**9 + 1  
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if pair(mid) >= border_median:
            ok = mid
        else:
            ng = mid
    ans = ok
    return ans

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

Solution (Python):
def d_median_of_medians(N, A):
    class BIT(object):
        def __init__(self, n):
            self.size = n
            self.tree = [0] * (self.size + 1)

        def __str__(self):
            return '[{}]'.format(', '.join(map(str, self.tree)))

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

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

    def pair(x):
        a_prime = [-1] * N
        for k in range(N):
            if A[k] >= x:
                a_prime[k] = 1  

        s = [0]
        min_s = 0
        max_s = 0
        tmp = 0
        
        for a in a_prime:
            tmp += a
            min_s = min(min_s, tmp)
            max_s = max(max_s, tmp)
            s.append(tmp)

        bit_size = max_s - min_s + 1  
        bit = BIT(bit_size)
        ans = 0
        for sk in s:
            sk -= (min_s - 1)  
            ans += bit.sum(sk)
            bit.add(sk, 1)
        return ans

    
    border_median = (N * (N + 1) // 2 + 1) // 2
    ok = 0
    ng = 10**9 + 3
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if pair(mid) >= border_median:
            ok = mid
        else:
            ng = mid
    ans = ok
    return ans

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

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


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 reset(self):
        self.tree = [0] * (self.size + 1)


def solve(n, aaa):
    t = n * (n + 1) // 4
    alt = sorted(set(aaa))
    l, r = 0, len(alt) - 1
    bt = Bit(n * 2)
    while l <= r:
        m = (l + r) // 2
        am = alt[m]
        ccc = accumulate(1 if a - am >= 0 else -1 for a in aaa)
        bt.add(n, 1)
        right_order = 0
        for p in ccc:
            p += n
            right_order += bt.sum(p)
            bt.add(p, 1)
        if right_order >= t:
            l = m + 1
        else:
            r = m - 1
        bt.reset()
    return alt[r]


n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))

Solution (Python):


import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq





def solve(f):
    n = f.read_int()
    a = f.read_int_list()

    def check(num):
        aa = [10**5+1]*(n+1)
        for i, ai in enumerate(a):
            if ai < num:
                aa[i+1] = aa[i]-1
            else:
                aa[i+1] = aa[i]+1

        bit = BinaryIndexedTree(2*10**5+1)
        cnt = 0
        for i in xrange(n+1):
            cnt += bit.sum(aa[i])
            bit.add(aa[i], 1)

        return n*(n+1)/2 - cnt <= cnt

    mi = 0
    ma = 10**9+1

    while ma - mi > 1:
        mid = (ma+mi)/2
        if check(mid):
            mi = mid
        else:
            ma = mid

    return mi


class BinaryIndexedTree(object):
    """Binary Indexed Tree (1-indexed)"""
    def __init__(self, size, default=0):
        self.bit = [default for _ in range(size + 1)]
        self.size = size

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

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


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case 
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Solution (Python):


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

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


a_sorted = sorted(a_list)

left = 0
right = N
mid = N // 2
C = N*(N+1) // 2

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

Solution (Python):


import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq





def solve(f):
    n = f.read_int()
    a = f.read_int_list()

    if n == 1: return a[0]

    d = dict(zip(sorted(set(a)), range(len(a))))

    def check(num):
        a1 = [0]*(n+1)
        a2 = [0]*(n+1)
        for i, ai in enumerate(a):
            if ai < num:
                a1[i+1] = a1[i]+1
                a2[i+1] = a2[i]
            else:
                a1[i+1] = a1[i]
                a2[i+1] = a2[i]+1
        ad = [a2[i]-a1[i]+10**5+1 for i in xrange(n+1)]

        bit = BinaryIndexedTree(2*10**5+1)
        cnt = 0
        for i in xrange(n+1):
            cnt += bit.sum(ad[i])
            bit.add(ad[i], 1)
        

        return n*(n+1)/2 - cnt <= cnt

    mi = 0
    ma = 10**9+1

    while ma - mi > 1:
        mid = (ma+mi)/2
        if check(mid):
            mi = mid
        else:
            ma = mid

    return mi


class BinaryIndexedTree(object):
    """Binary Indexed Tree (1-indexed)"""
    def __init__(self, size, default=0):
        self.bit = [default for _ in range(size + 1)]
        self.size = size

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

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


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case 
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)