Problem:
 Score : 700 points    Problem Statement We will define the median of a sequence b of length M , as follows:   Let b' be the sequence obtained by sorting b in non-decreasing order. Then, the value of the (M / 2 + 1) -th element of b' is the median of b . Here, / is integer division, rounding down.   For example, the median of (10, 30, 20) is 20 ; the median of (10, 30, 20, 40) is 30 ; the median of (10, 10, 10, 20, 30) is 10 .  Snuke comes up with the following problem.  You are given a sequence a of length N .
For each pair (l, r) ( 1 \leq l \leq r \leq N ), let m_{l, r} be the median of the contiguous subsequence (a_l, a_{l + 1}, ..., a_r) of a .
We will list m_{l, r} for all pairs (l, r) to create a new sequence m .
Find the median of m .      Constraints  1 \leq N \leq 10^5  a_i is an integer.  1 \leq a_i \leq 10^9         Input Input is given from Standard Input in the following format:  N  a_1  a_2  ...  a_N       Output Print the median of m .        Sample Input 1 3
10 30 20      Sample Output 1 30  The median of each contiguous subsequence of a is as follows:   The median of (10) is 10 .  The median of (30) is 30 .  The median of (20) is 20 .  The median of (10, 30) is 30 .  The median of (30, 20) is 30 .  The median of (10, 30, 20) is 20 .   Thus, m = (10, 30, 20, 30, 30, 20) and the median of m is 30 .       Sample Input 2 1
10      Sample Output 2 10       Sample Input 3 10
5 9 5 9 8 9 3 5 4 3      Sample Output 3 8

Solution (Python):



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




def mergesort(S, f, t):
    global T

    if t - f <= 1:
        return 0

    mid = (f + t) // 2
    n1 = mergesort(S, f, mid)
    n2 = mergesort(S, mid, t)
    n = n1 + n2
    i = f
    j = mid
    k = f
    while i < mid and j < t:
        if S[i] <= S[j]:
            T[k] = S[i]
            i += 1
            n += t - j
        else:
            T[k] = S[j]
            j += 1
        k += 1

    while i < mid:
        T[k] = S[i]
        i += 1
        k += 1
    assert k == j
    for i in range(f, k):
        S[i] = T[i]
    return n

def inversion(S):
    """リストSの転倒数"""
    global T
    T = [0] * len(S)
    return mergesort(S, 0, len(S))

def n_median_larger_than_or_equal_to(x):
    """aの部分列の中央値のうちx以上のものの個数"""

    
    b = [-1 if e < x else 1 for e in a]
    
    S = [0]
    for e in b:
        S.append(S[-1] + e)
    
    return inversion(S)


lo = 1
hi = max(a)

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

while lo < hi:
    mid = (lo + hi + 1) // 2
    nm = n_median_larger_than_or_equal_to(mid)
    if nm >= (ncomb + 1) // 2:
        lo = mid
    else:
        hi = mid - 1

print(lo)

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):
N = int(input())
a = [int(x) for x in input().split()]

b = sorted(a)
M = ((N + 1) * N // 2 + 1) // 2


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

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

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


def is_OK(x):
    S = [1] * N
    for i in range(N):
        if a[i] < x:
            S[i] = -1
        if i > 0:
            S[i] += S[i - 1]
    S = [0] + S
    min_S = min(S)
    max_S = max(S)

    bit = BIT(max_S - min_S + 1)
    cnt = 0
    for S_i in S:
        S_i = S_i - min_S + 1
        cnt += bit.sum(S_i)
        bit.add(S_i, 1)
    return cnt >= M


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

print(left)

Solution (Python):

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

def solve(x):
    data = [0]*(N+1)
    def add(k, x):
        while k <= N:
            data[k] += x
            k += k & -k
    def get(k):
        s = 0
        while k:
            s += data[k]
            k -= k & -k
        return s
    c = 0; d = 10**18
    for a in A:
        if x <= a:
            c += 1
        else:
            c -= 1
        d = min(c, d)
    res = N*(N+1)//2
    c = -d+1
    for a in A:
        res -= get(c)
        if x <= a:
            c += 1
        else:
            c -= 1
        add(c, 1)
    return res <= N*(N+1)//4

left = min(A); right = max(A)+1
while left+1 < right:
    mid = (left + right) // 2
    if solve(mid):
        left = mid
    else:
        right = mid
print(left)

Solution (Python):
'''
☆長さnの数列Aの中央値がxであるとは
１．x以上の要素が (n + 1)// 2 個以上
２．そのようなxの中で最小
ということ。
'''

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

    def sum(self, i):
        '''
        :param i: 
        :return: bit[i]までの和
        '''
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, x):
        '''
        :param i:
        :param x:
        :return: bit[i]にxを加える
        '''

        while i < len(self.bit):
            self.bit[i] += x
            i += i & -i

'''
def median(L):
    n = len(L)
    L.sort()
    return L[n // 2]
'''

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

def ans_bigger(X):
    '''
    答えがX以上かどうかを判定
    つまり、区間[l. r]のうち中央値がX以上であるものが ((N+1) * N /2 + 1 ) //2 個以上かを判定
    [l, r]の中央値がX以上 =
    '''
    a_X = [1 if a[i] >= X else -1 for i in range(N)]
    cum = [N]
    for i in range(N):
        cum.append(cum[i] + a_X[i]) 
    b = BIT(2 * N + 1)
    ans = 0
    for j in range(N + 1):
        ans += b.sum(cum[j])
        b.add(cum[j], 1)
    if ans >= ((N+1) * N /2 + 1 ) //2:
        return True
    else:
        return False

l = min(a)
r = max(a) + 1

while r > l + 1:
    if ans_bigger((l + r) // 2):
        l = (l + r) // 2
    else:
        r = (l + r) // 2
print(l)