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):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
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 = 10 ** 9 + 7


n = I()
A = LI()


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 > 0:
            res += self.bit[x - 1]
            x -= x & -x
        return res



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):
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):
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
            l, m = m, (m + r) // 2
        else:
            m, r = (m + l) // 2, m + 1

    print(B[m])


if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    n, i = LI()
    print(n-i+1)
    return


def B():
    h, w = LI()
    a = SR(h)
    dy = defaultdict(int)
    dx = defaultdict(int)
    for y in range(h):
        for x in range(w):
            if a[y][x] == "
                dx[x] = 1
                dy[y] = 1
    dy = list(sorted(dy.items(), key=lambda x: x[0]))
    dx = list(sorted(dx.items(), key=lambda x: x[0]))
    for y,_ in dy:
        for x,_ in dx:
            print(a[y][x], end="")
        print()
    return


def C():
    n, k = LI()
    x = LI()
    ans = inf
    for i in range(n - k + 1):
        if x[i] * x[i + k - 1] > 0:
            ans = min(ans, max(abs(x[i]), abs(x[i + k - 1])))
            continue
        ans = min(ans, min(abs(x[i]), abs(x[i + k - 1])) * 2 + max(abs(x[i]), abs(x[i + k - 1])))
    print(ans)
    return









































def D():
    class BinaryIndexedTree:
        
        def __init__(self, size):
            """
            :param int size:
            """
            self.bit = [0 for _ in range(size)]
            self.size = size

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

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

        def __len__(self):
            return self.size
            
    def count_inversions(array, Max=None):
        """
        リストから転倒数 (array[i] > array[j] (i < j) となる (i, j) の組み合わせ数) を返す
        バブルソートするときに反転する必要がある数。
        :param list of int array:
                すべての要素が 0 以上の int である配列。
        :param int max: array の最大値。指定はわかる場合
        :rtype: int
        """
        if not Max:
            Max = max(array) + n
        bit = BinaryIndexedTree(Max + 1)
        res = 0
        for i in range(len(array)):
            res += i - bit.sum(array[i])
            bit.add(array[i], 1)
        return res

    def f(i):
        x = a_sorted[i]
        c = [n] + [1 if e >= x else - 1 for e in a]
        for i in range(n):
            c[i + 1] += c[i]
        tmp = count_inversions(c, 2 * n)
        if invmax - tmp >= (invmax + 1) // 2:
            return True
        else:
            return False
        
        
        
    
    n = II()
    a = LI()
    a_sorted = sorted(a)
    invmax = (n + 1) * n // 2

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

if __name__ == '__main__':
    D()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    n, i = LI()
    print(n-i+1)
    return


def B():
    h, w = LI()
    a = SR(h)
    dy = defaultdict(int)
    dx = defaultdict(int)
    for y in range(h):
        for x in range(w):
            if a[y][x] == "
                dx[x] = 1
                dy[y] = 1
    dy = list(sorted(dy.items(), key=lambda x: x[0]))
    dx = list(sorted(dx.items(), key=lambda x: x[0]))
    for y,_ in dy:
        for x,_ in dx:
            print(a[y][x], end="")
        print()
    return


def C():
    n, k = LI()
    x = LI()
    ans = inf
    for i in range(n - k + 1):
        if x[i] * x[i + k - 1] > 0:
            ans = min(ans, max(abs(x[i]), abs(x[i + k - 1])))
            continue
        ans = min(ans, min(abs(x[i]), abs(x[i + k - 1])) * 2 + max(abs(x[i]), abs(x[i + k - 1])))
    print(ans)
    return



def D():
    class BinaBinaryIndexedTree:
        
        def __init__(self, size):
            """
            :param int size:
            """
            self.bit = [0 for _ in range(size)]
            self.size = size

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

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

        def __len__(self):
            return self.size 

    def count_inversions(array, Max=None):
        """
        リストから転倒数 (array[i] > array[j] (i < j) となる (i, j) の組み合わせ数) を返す
        バブルソートするときに反転する必要がある数。
        :param list of int array:
                すべての要素が 0 以上の int である配列。
        :param int max: array の最大値。指定はわかる場合
        :rtype: int
        """
        if not Max:
            Max = max(array) + n
        bit = BinaBinaryIndexedTree(Max + 1)
        res = 0
        for i in range(len(array)):
            res += i - bit.sum(array[i])
            bit.add(array[i], 1)
        return res

    def f(i):
        x = a_sorted[i]
        c = [n] + [1 if e >= x else - 1 for e in a]
        for i in range(n):
            c[i + 1] += c[i]
        tmp = count_inversions(c, 2 * n)
        if invmax - tmp >= (invmax + 1) // 2:
            return True
        else:
            return False
        
        
        
    
    n = II()
    a = LI()
    a_sorted = sorted(a)
    invmax = (n + 1) * n // 2

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

if __name__ == '__main__':
    D()

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):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i



le = -1
ri = max(A) + 1
mid = (le + ri) // 2
while ri - le > 1:
    S = [0] * n
    S[0] = -1 + 2 * int(A[0] >= mid)
    for i in range(n-1):
        S[i+1] = S[i] - 1 + 2 * int(A[i+1] >= mid)
    bit = Bit(n+2)
    ans = 0
    for i in range(n):
        if S[i] >= 0:
            ans += 1

    

    Smin = min(S)
    S = [S[i] - Smin + 1 for i in range(n)]

    
    
    for i, p in enumerate(S):
        
        bit.add(p, 1)

        ans += bit.sum(p) - 1  
        


    

    if ans >= (n*(n+1))//(2*2):
        le = mid
    else:
        ri = mid
    mid = (le + ri) // 2

print(le)

Solution (Python):
def f(n, a):
    x = list(sorted(set(a)))
    n_sub_half = n * (n + 1) // 2 // 2
    n_plus_minus = n * 2 + 1
    Li = 0
    Ri = len(x)
    while Ri > Li + 1:
        i = (Li + Ri) // 2
        xi = x[i]
        cnt_sum = [0] * n_plus_minus
        cumsum = 0
        cnt_sum[cumsum] = 1
        judge = 0
        s = 0
        for ak in a:
            if ak >= xi:
                cumsum += 1
                s += cnt_sum[cumsum] + 1
            else:
                cumsum -= 1
                s -= cnt_sum[cumsum + 1] - 1
            cnt_sum[cumsum] += 1
            judge += s
            if judge >= n_sub_half:
                Li = i
                break
        else:
            Ri = i
    print(x[Li])

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

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

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

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)
        
    def update(self, i, v):
        while i <= self.n:
            self.bit[i] += v
            i += i & -i
            
    def query(self, i):
        ret = 0
        while i > 0:
            ret += self.bit[i]
            i -= i & -i
        return ret
    
    def reset(self):
        self.bit = [0] * (self.n + 1)

ub = max(a) + 1
lb = 0
th = ceil(((N + 1) * N // 2) / 2)
bit = BIT(N + 1)

while ub - lb > 1:
    mid = (ub + lb) // 2
    b = [1 if v >= mid else -1 for v in a]
    b = [0] + list(accumulate(b))
    b_sorted = {v: i + 1 for i, v in enumerate(sorted(b))}
    
    
    cnt = 0
    bit.reset()
    for v in b:
        cnt += bit.query(b_sorted[v])
        bit.update(b_sorted[v], 1)
        
    if cnt >= th:
        lb = mid
    else:
        ub = mid
    
print(lb)

Solution (Python):
import numpy as np
from collections import defaultdict

N = int(input())
A = np.array(input().split(), dtype=np.int32)
total_medians = N*(N+1)//2



def test(x):
  
  
  
  
  current = 0 
  memo = defaultdict(int) 
  memo[0] = 1
  cnt_below = 1 
  result = 0
  for a in A:
    if a > x:
      current += 1
      cnt_below += memo[current]
    else:
      cnt_below -= memo[current]
      current -= 1
    result += cnt_below
    memo[current] += 1
    cnt_below += 1
  return result <= (total_medians-1)//2

AA = sorted(A)
left = -1 
right = len(AA)-1 
while right - left > 1:
  mid = (left+right)//2
  if test(AA[mid]):
    right = mid
  else:
    left = mid
    
answer = AA[right]
print(answer)

Solution (Python):
N = int(input())
A = [int(x) for x in input().split()]
total_medians = N*(N+1)//2



def BIT_update(BIT,x,value):
  
  L = len(BIT)
  while x < L:
    BIT[x] += value
    bottom_bit = x & (-x)
    x += bottom_bit
  return

def BIT_sum(BIT,x):
  
  result = 0
  while x:
    result += BIT[x]
    bottom_bit = x & (-x)
    x -= bottom_bit
  return result

def test(x):
  
  
  B = [0]
  for a in A:
    B.append(B[-1] + (1 if a>x else -1))
  m = min(B)-1
  B = [x-m for x in B]

  BIT = [0]*(N+1)
  
  cnt = 0
  for R in range(1,N+1):
    BIT_update(BIT,B[R-1],1)
    cnt += BIT_sum(BIT,B[R]) 
  return cnt <= (total_medians-1)//2

AA = sorted(A)
left = -1 
right = len(AA)-1 
while right - left > 1:
  mid = (left+right)//2
  if test(AA[mid]):
    right = mid
  else:
    left = mid
answer = AA[right]

print(answer)

Solution (Python):

import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


class BinaryIndexTree:
    def __init__(self, n):
        self._size = n
        self._tree = [0] * (n+1)

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

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


def solve(N: int, a: "List[int]"):
    c = N * (N + 1) // 2
    th = (c + 1) // 2

    xs = list(sorted(set(a)))
    lo = 0
    hi = len(xs)

    def _f(x):
        ss = [0] + list(accumulate([1 if x <= v else -1 for v in a]))
        n = max([abs(s) for s in ss])
        bit = BinaryIndexTree(2 * n + 1)

        ret = 0
        for s in ss:
            ret += bit.sum(s + n) 
            bit.add(s + n, 1)
        return ret

    while (lo + 1) < hi:
        mid = (lo + hi) // 2
        if th <= _f(xs[mid]):
            lo = mid
        else:
            hi = mid
    return xs[lo]


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) ]  
    result = solve(N, a)
    print(result)

if __name__ == '__main__':
    main()

Solution (Python):
def f(n, a):
    x = list(sorted(set(a)))
    n_sub_half = n * (n + 1) // 2 // 2
    n_plus_minus = n * 2 + 1
    Li = 0
    Ri = len(x)
    while Ri > Li + 1:
        i = (Li + Ri) // 2
        xi = x[i]
        cnt_sum = [0] * n_plus_minus
        cumsum = 0
        cnt_sum[cumsum] = 1
        judge = 0
        s = 0
        for ak in a:
            if ak >= xi:
                cumsum += 1
                s += cnt_sum[cumsum] + 1
            else:
                cumsum -= 1
                s -= cnt_sum[cumsum + 1] - 1
            cnt_sum[cumsum] += 1
            judge += s
            if judge >= n_sub_half:
                Li = i
                break
        else:
            Ri = i
    print(x[Li])


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

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

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

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

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

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

N=INT()
A=LIST()

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


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

def calc(X):
    
    L=[0]*N
    for i in range(N):
        if A[i]>=X:
            L[i]=1
        else:
            L[i]=-1
    
    sm=[0]+list(accumulate(L))
    
    
    ans=ALL-get_inv(sm)
    
    return ans>=ceil(ALL, 2)


A2=sorted(set(A))
low=0
hi=len(A2)
while low+1<hi:
    mid=(hi+low)//2
    if calc(A2[mid]):
        low=mid
    else:
        hi=mid

print(A2[low])

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

get_ints = lambda: [int(st) for st in input().split()]
N=int(input())
inarr=get_ints()
sorted_in = sorted(inarr)
comb = N*(N+1) // 4

bit = Bit(2*N+1)
def binsearch(lft, rgt):
    half = (lft + rgt) // 2
    if lft >= half:
        return half
    summed = 0
    res = 0
    bit.reset()
    bit.add(N, 1)
    for x in inarr:
        value = 1 if x >= sorted_in[half] else -1
        summed += value
        count = bit.sum(N + summed)
        bit.add(N + summed, 1)
        res += count
    return binsearch(half, rgt) if res >= comb else binsearch(lft, half)

res = binsearch(0, N)
print(sorted_in[res])

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

get_ints = lambda: [int(st) for st in input().split()]
N=int(input())
inarr=get_ints()
sorted_in = sorted(inarr)
comb = N*(N+1) // 2

bit = Bit(2*N+1)
def binsearch(lft, rgt):
    half = (lft + rgt) // 2
    if lft >= half:
        return half
    summed = 0
    res = 0
    bit.reset()
    bit.add(N, 1)
    for x in inarr:
        value = 1 if x >= sorted_in[half] else -1
        summed += value
        count = bit.sum(N + summed)
        bit.add(N + summed, 1)
        res += count
    return binsearch(half, rgt) if res >= comb // 2 else binsearch(lft, half)

res = binsearch(0, N)
print(sorted_in[res])

Solution (Python):
import math
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):
        t = self.tree
        for i in range(len(t)):
            t[i] = 0

get_ints = lambda: [int(st) for st in input().split()]
N=int(input())
inarr=get_ints()
sorted_in = sorted(inarr)
comb = N*(N+1) // 2

bit = Bit(2*N+1)
def binsearch(lft, rgt):
    half = (lft + rgt) // 2
    if lft >= half:
        return half
    summed = 0
    res = 0
    bit.reset()
    bit.add(N, 1)
    for x in inarr:
        value = 1 if x >= sorted_in[half] else -1
        summed += value
        count = bit.sum(N + summed)
        bit.add(N + summed, 1)
        res += count
    return binsearch(half, rgt) if res >= math.ceil(comb/2) else binsearch(lft, half)

res = binsearch(0, N)
print(sorted_in[res])

Solution (Python):
import math
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):
        for i in range(len(self.tree)):
            self.tree[i] = 0

get_ints = lambda: [int(st) for st in input().split()]
N=int(input())
inarr=get_ints()
sorted_in = sorted(inarr)
comb = N*(N+1) // 2

bit = Bit(2*N+1)
def binsearch(lft, rgt):
    half = (lft + rgt) // 2
    if lft >= half:
        return half
    summed = 0
    res = 0
    bit.reset()
    bit.add(N, 1)
    for x in inarr:
        value = 1 if x >= sorted_in[half] else -1
        summed += value
        count = bit.sum(N + summed)
        bit.add(N + summed, 1)
        res += count
    return binsearch(half, rgt) if res >= math.ceil(comb/2) else binsearch(lft, half)

res = binsearch(0, N)
print(sorted_in[res])

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

get_ints = lambda: [int(st) for st in input().split()]
N=int(input())
inarr=get_ints()

sorted_in = sorted(inarr)

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

def binsearch(lft, rgt):
    half = (lft + rgt) // 2
    
    if lft >= half:
        return half
    summed = 0
    res = 0

    bit = Bit(2*N+1)
    bit.add(N, 1)
    for i, x in enumerate(inarr):
        value = 1 if x >= sorted_in[half] else -1
        summed += value
        
        count = bit.sum(N + summed)
        bit.add(N + summed, 1)
        res += count

    
    if res >= math.ceil(comb/2):
        return binsearch(half, rgt)
    else:
        return binsearch(lft, half)


res = binsearch(0, N)

print(sorted_in[res])

Solution (Python):
def bisect_right_callable(fn, x, lo, hi):
    """
    lo から hi-1 のうち、fn の結果が x 以下となる、最も右の値 + 1
    bisect.bisect_right と同じ
    https://docs.python.org/ja/3/library/bisect.html
    :param callable fn:
    :param x:
    :param int lo: 最小値
    :param int hi: 最大値 + 1
    :return: lo <= ret <= hi
    """
    while lo < hi:
        mid = (lo + hi) // 2
        if x < fn(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo


N = int(input())
series = list(map(int, input().split()))
series_sorted = sorted(series)


lr_size = (N + 1) * N / 2


def count_lr(x):
    """
    x 以上の数を半分以上含む == 中央値が x 以上である、L と r の選び方の数
    :param x:
    :return:
    """
    ret = 0
    
    cumsum = 0
    
    counts = {i: 0 for i in range(-N, N + 1)}
    counts[cumsum] = 1
    diff = 0
    for i in range(N):
        if series[i] >= x:
            cumsum += 1
            counts[cumsum] += 1
            diff += counts[cumsum]
        else:
            cumsum -= 1
            counts[cumsum] += 1
            diff -= counts[cumsum + 1] - 1
        ret += diff
    return ret




def solve(i):
    if count_lr(series_sorted[i]) >= (lr_size + 1) // 2:
        return 0
    else:
        return float('inf')


ans_i = bisect_right_callable(solve, 0, lo=0, hi=N)
print(series_sorted[max(0, min(N - 1, ans_i - 1))])

Solution (Python):
def cumsum(li):
    ret = []
    sum = 0
    for i in li:
        sum += i
        ret.append(sum)
    return ret


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

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

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

    def __len__(self):
        return self._size


def count_inversions(li, max=None):
    """
    リストから転倒数 (li[i] > li[j] (i < j) となる (i, j) の組み合わせ数) を返す
    バブルソートするときに反転する必要がある数。
    :param numpy.ndarray | list of int li:
            すべての要素が 0 以上の int である配列。
            BIT を使うので、マイナスを含んだり最大値が大きい場合は np.argsort の結果を指定
            ただしリストに重複を含む場合は np.argsort は unstable なので別の方法使うこと
            https://docs.scipy.org/doc/numpy/reference/generated/numpy.sort.html
    :param int max: li の最大値。わかる場合は指定
    :rtype: int
    """
    if not max:
        max = __builtins__.max(li)
    bit = BinaryIndexedTree(size=max + 1)
    ret = 0
    for i in range(len(li)):
        ret += i - bit.sum(li[i])
        bit.add(li[i], 1)
    return ret


def bisect_left_callable(fn, x, lo, hi):
    """
    lo から hi-1 のうち、fn の結果が x 以上となる、最も左の値
    bisect.bisect_left と同じ
    https://docs.python.org/ja/3/library/bisect.html
    :param callable fn:
    :param x:
    :param int lo: 最小値
    :param int hi: 最大値 + 1
    :return: lo <= ret <= hi
    """
    while lo < hi:
        mid = (lo + hi) // 2
        if fn(mid) < x:
            lo = mid + 1
        else:
            hi = mid
    return lo


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

series_sorted = sorted(series)


lr_size = (N + 1) * N / 2





def solve(i):
    x = series_sorted[i]
    
    cumsum_li = [0] + cumsum([1 if s >= x else -1 for s in series])
    
    inversions = count_inversions([N + i for i in cumsum_li], max=N + N)
    if lr_size - inversions >= (lr_size + 1) // 2:
        return i
    else:
        return float('inf')


ans_i = bisect_left_callable(solve, float('inf'), lo=0, hi=N)
print(series_sorted[max(0, min(N - 1, ans_i - 1))])

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


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

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

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

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


BIT = BinaryIndexedTree(N + 1)  

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

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

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

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

print(ok)