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



Sample input:
3
10 30 20


Sample output:
30

Submission status: Time Limit Exceeded

Solution code:
class BIT:
    """1-indexed BIT
    """

    def __init__(self, size: int):
        """サイズを指定して BIT を初期化します。
        """
        # BIT のサイズは 2^n + 1
        self.__size = size

        # 実際の配列
        self.__bit = [0] * (self.__size+1)

    def add(self, idx: int, val: int):
        """位置 idx (1-indexed) に値 val をたす。
        :param idx: 値を追加したいインデックス
        :param val: 追加したい値
        """
        while idx <= self.__size:
            self.__bit[idx] += val
            idx += idx & (-idx)

    def sum(self, l: int, r: int)->int:
        """(l, r] の累積和を計算する。
        :param l: left index
        :param r: right index
        :return: (l, r] の累積和
        """
        return self.__sum__(r) - self.__sum__(l)

    def __sum__(self, idx: int)->int:
        s = 0
        while idx > 0:
            s += self.__bit[idx]
            idx -= idx & (-idx)
        return s


def inversion(A: list) -> int:
    bit = BIT(max(A))
    s = 0
    for a in A:
        s += bit.sum(0, a)
        bit.add(a, 1)

    return s


def check(A: list, x: int)->int:
    n = len(A)
    S = [0] * (n + 1)
    for i in range(n):
        if x <= A[i]:
            S[i + 1] = S[i] + 1
        else:
            S[i + 1] = S[i] - 1

    m = min(S)
    return inversion([s - (m - 1) for s in S])


def median_of_medians(N: int, A: list)->int:
    alpha = sorted(A)
    l, r = 0, N
    while r - l > 1:
        m = (r + l + 1) // 2
        if 2*check(A, alpha[m]) >= (N * (N + 1)) // 2:
            l = m
        else:
            r = m

    return alpha[l]


if __name__ == "__main__":
    N = int(input())
    A = [int(s) for s in input().split()]
    ans = median_of_medians(N, A)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
class BIT:
    """1-indexed BIT
    """

    def __init__(self, size: int):
        """サイズを指定して BIT を初期化します。
        """
        # BIT のサイズは 2^n + 1
        self.__size = 1
        while self.__size < size:
            self.__size *= 2
        self.__size += 1

        # 実際の配列
        self.__bit = [0] * self.__size

    def add(self, idx: int, val: int):
        """位置 idx (1-indexed) に値 val をたす。
        :param idx: 値を追加したいインデックス
        :param val: 追加したい値
        """
        while idx < self.__size:
            self.__bit[idx] += val
            idx += idx & (-idx)

    def sum(self, l: int, r: int)->int:
        """(l, r] の累積和を計算する。
        :param l: left index
        :param r: right index
        :return: (l, r] の累積和
        """
        return self.__sum__(r) - self.__sum__(l)

    def __sum__(self, idx: int)->int:
        s = 0
        while idx > 0:
            s += self.__bit[idx]
            idx -= idx & (-idx)
        return s


def convert(A: list)->list:
    B = sorted(A)
    C = []
    N = len(A)
    for a in A:
        l, r = 0, N
        while 1 < r - l:
            m = (l+r)//2
            if a < B[m]:
                r = m
            else:
                l = m
        C.append(r)
    return C


def inversion(A: list)->int:
    n = len(A)
    _A = convert(A)
    bit = BIT(n)
    s = 0
    for j, a in enumerate(_A):
        s += j - bit.sum(0, a)
        bit.add(a, 1)
    return s


def check(A: list, x: int)->int:
    # n = len(A)
    # bit = BIT(n)
    # for i, a in enumerate(A):
    #     bit.add(i+1, 1 if a >= x else -1)

    s = 0
    B = []
    for a in A:
        s += 1 if a >= x else -1
        B.append(s)
    return inversion(B)
    # return inversion([bit.sum(0, i+1) for i in range(n)])


def median_of_medians(N: int, A: list)->int:
    alpha = sorted(A)
    l, r = 0, N
    m, c = N//2, N*(N+1)//2
    while True:
        if check(A, alpha[m]) <= c//2:
            if m == N-1:
                break
            elif check(A, alpha[m+1]) > c//2:
                break
            else:
                l, m = m, (m+r)//2
        else:
            m, r = (m+l)//2, m+1

    return alpha[m]


if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    ans = median_of_medians(N, A)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
class BIT:
    """1-indexed BIT
    """

    def __init__(self, size: int):
        """サイズを指定して BIT を初期化します。
        """
        # BIT のサイズは 2^n + 1
        self.__size = 1
        while self.__size < size:
            self.__size *= 2
        self.__size += 1

        # 実際の配列
        self.__bit = [0] * self.__size

    def add(self, idx: int, val: int):
        """位置 idx (1-indexed) に値 val をたす。
        :param idx: 値を追加したいインデックス
        :param val: 追加したい値
        """
        while idx < self.__size:
            self.__bit[idx] += val
            idx += idx & (-idx)

    def sum(self, l: int, r: int)->int:
        """(l, r] の累積和を計算する。
        :param l: left index
        :param r: right index
        :return: (l, r] の累積和
        """
        return self.__sum__(r) - self.__sum__(l)

    def __sum__(self, idx: int)->int:
        s = 0
        while idx > 0:
            s += self.__bit[idx]
            idx -= idx & (-idx)
        return s


def convert(A: list)->list:
    B = sorted(A)
    C = []
    N = len(A)
    for a in A:
        l, r = 0, N
        while 1 < r - l:
            m = (l+r)//2
            if a <= B[m]:
                r = m
            else:
                l = m
        C.append(r)
    return C


def inversion(A: list)->int:
    n = len(A)
    _A = convert(A)
    bit = BIT(n)
    s = 0
    for j, a in enumerate(_A):
        s += j - bit.sum(0, a)
        bit.add(a, 1)
    return s


def check(A: list, x: int)->int:
    n = len(A)
    bit = BIT(n)
    for i, a in enumerate(A):
        bit.add(i+1, 1 if a >= x else -1)
    return inversion([bit.sum(0, i+1) for i in range(n)])


def median_of_medians(N: int, A: list)->int:
    alpha = sorted(A)
    l, r = 0, N
    m, c = N//2, N*(N+1)//2
    while True:
        if check(A, alpha[m]) <= c//2:
            if m == N-1:
                break
            elif check(A, alpha[m+1]) > c//2:
                break
            else:
                l, m = m, (m+r)//2
        else:
            m, r = (m+l)//2, m+1

    return alpha[m]


if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    ans = median_of_medians(N, A)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input()) 
A = [int(i) for i in input().split()]
A.sort()

def f(x):
    B = [((x<=a)<<1)-1 for a in A]      
    C = [0]  
    [C.append(C[-1]+b) for b in B]          
    r = 0
    s = 0
    for i in range(N):
        for j in range(i+1,N+1):
            s += 1
            if C[j]-C[i] > 0: 
                r += 1
    return(r>s//2)        

l = 0
r = N-1
while l != r:
    if f((l+r)//2):               
        l = (l+r)//2 + 1
    else:
        r = (l+r)//2
print(A[r])

Submission status: Time Limit Exceeded

Solution code:
import copy

def solve():
    N = int(input())
    a = list(map(int, input().split()))
    s = {}
    for ai in a:
        if ai in s.keys():
            s[ai] += 1
        else:
            s[ai] = 1

    skeys = sorted(list(s.keys()))
    t = copy.copy(s)

    for i in range(2, N+1):
        #print(s)
        if i % 2 == 0:
            t[a[i // 2 - 1]] -= 1
        else:
            t[a[N - i // 2]] -= 1
        for k in skeys:
            s[k] += t[k]

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

    #print(target)
    #print(s)
    for k in skeys:
        if target > s[k]:
            target -= s[k]
        else:
            return k

ans = solve()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(int, input().split()))
s = []
for i in range(1, N+1):
    left = i // 2
    right = N - (i - 1) // 2
    s += a[left:right]
s.sort()
scnt = len(s)
print(s[scnt // 2])

Submission status: Time Limit Exceeded

Solution code:
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 med(x):
    cum = [0] * (n+1)
    for i in range(n):
        if a[i] >= x:
            cum[i+1] = cum[i] + 1
        else:
            cum[i+1] = cum[i] - 1
    m = min(cum)
    for i in range(n+1):
        cum[i] -= m - 1
    zb = Bit(max(cum))
    ret = 0
    for j in range(n+1):
        ret += zb.sum(cum[j])
        zb.add(cum[j], 1)
    return ret
b = sorted(a)
l = 0
r = n
while(r - l > 1):
    mid = (l + r) // 2
    if 2 * med(b[mid]) >= n * (n+1) // 2:
        l = mid
    else:
        r = mid
print(b[l])

Submission status: Time Limit Exceeded

Solution code:
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 med(x):
    cum = [0] * (n+1)
    for i in range(n):
        if a[i] >= x:
            cum[i+1] = cum[i] + 1
        else:
            cum[i+1] = cum[i] - 1
    m = min(cum)
    for i in range(n+1):
        cum[i] -= m - 1
    zb = Bit(max(cum))
    ret = 0
    for j in range(n+1):
        ret += zb.sum(cum[j])
        zb.add(cum[j], 1)
    return ret
l = min(a)
r = max(a) + 1
while(r - l > 1):
    mid = (r+l) // 2
    if 2 * med(mid) >= n * (n+1) // 2:
        l = mid
    else:
        r = mid
print(l)

Submission status: Time Limit Exceeded

Solution code:
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 zip(l):
    s = sorted(list(enumerate(l)), key = lambda x: x[1])
    ret = [0] * len(l)
    pre = -(10 ** 10)
    rank = 0
    for i, e in s:
        if e > pre:
            rank += 1
            pre = e
        ret[i] = rank
    return ret
def med(x):
    cum = [0] * (n+1)
    for i in range(n):
        if a[i] >= x:
            cum[i+1] = cum[i] + 1
        else:
            cum[i+1] = cum[i] - 1
    z = zip(cum)
    nz = max(z)
    zb = Bit(nz)
    ret = 0
    for j in range(n+1):
        ret += zb.sum(z[j])
        zb.add(z[j], 1)
    return ret
l = min(a)
r = max(a) + 1
while(r - l > 1):
    mid = (r+l) // 2
    if 2 * med(mid) >= n * (n+1) // 2:
        l = mid
    else:
        r = mid
print(l)

Submission status: Time Limit Exceeded

Solution code:
import statistics
n = int(input())
a = list(map(int, input().split()))
b = []
for l in range(n):
    for r in range(l,n):
        b.append(a[(l+r+1)//2])
b.sort()
print(b[len(b)//2])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
aList = [int(x) for x in input().split()]

cacheList = []
cacheList.extend(aList)
for i in range(2,N+1):
    for j in range(N):
        if i+j >= len(aList):
            break
        target = aList[j:j+i]
        cacheList.append(target[len(target)//2])

cacheList.sort()
print(cacheList[len(cacheList)//2])

Submission status: Time Limit Exceeded

Solution code:
int_n = int(input())
li_a = list(map(int, input().split()))


def cyuoh(target):
    sorted_target = sorted(target)
    idx = (len(target) // 2 + 1) - 1
    return sorted_target[idx]


# 連続部分列の列挙
li_m = list()

for l in range(int_n + 1):
    for r in range(l + 1, int_n + 1):
        li_m.append(cyuoh(li_a[l:r]))


print(cyuoh(li_m))

Submission status: Time Limit Exceeded

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
# N,M = map(int, input().split())
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
# A = sorted(A)
# print(A)
# print(Counter(A))

newmidlist = []
# 3 -> 1 // len // 2
# 2 -> 1    len // 2
# 4 -> 2 // 

# print(A)
for l in range(0, N):
    for r in range(l, N):
        # print(sorted( A[l:r+1]), "   " * (12 - (r+1-l)), sorted(A[l:r+1])[(r-l+1)//2])
        newmidlist.append ( sorted( A[l:r+1])[( r-l+1)//2 ]  )
# print(sorted(newmidlist)) 
print( sorted(newmidlist)[(len(newmidlist))//2] )

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from math import ceil, floor


class Solver(object):
    def __init__(self):
        self.n = int(input())
        self.a_s = list(map(int, input().split(" ")))
        self.m_length = 0

    def solve(self):
        m_s = []
        for i in range(1, self.n+1):  # 1 .. n
            left, right = self.compute_median_range(i)  # 1 .. n
            m_s.append(self.compute_median(left-1, right))
        m_s.sort()
        length = len(m_s)
        print(m_s[floor(length/2)])
            
    def compute_median(self, left, right):  # 0-index, inclusive
        subset = sorted(self.a_s[left:right+1])
        length = len(subset)
        return subset[floor(length/2)]

    def compute_median_range(self, length):  # 1-index
        # Use 1-index during computation
        left = ceil((length+1)/2)
        right = self.n - 1 - floor((length-1)/2)
        self.m_length += right - left + 1
        return left, right


if __name__ == "__main__":
    s = Solver()
    s.solve()

Submission status: Time Limit Exceeded

Solution code:
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でLSB(least significant bit/最下位 bit)が求まる
            #区間和はLSBだけ引いていく
            i -= i & -i
        return s

    #a_i(1<=i<=n)にxを加算
    #点に対する更新
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

def invnumber(n, S):
    bit = Bit(2*n+1)
    invs = 0
    for i in range(n):
        s = S[i]+n #BITで扱うため
        invs += bit.sum(s) # #i<j
        bit.add(s, 1)
    return invs

n = int(input())
a = list(map(int, input().split()))
r = max(a)+1
l = 0
c = (n*(n+1)//2+1)//2
while r-l > 1:
    m = (l+r)//2
    S = [0]*(n+1)
    for i in range(1, n+1):
        if a[i-1] >= m:
            S[i] = S[i-1] + 1
        else:
            S[i] = S[i-1] - 1
    if invnumber(n+1, S) >= c:
        l = m
    else:
        r = m
print(l)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

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

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

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

def check(a, v):
    global N

    bit = Bit(201010)
    offset = 100000

    sm = 0
    tot = 0
    bit.add(offset, 1)
    for i in range(N):
        tot += 1 if v <= a[i] else -1

        sm += bit.sum(tot + offset + 1)
        bit.add(tot + offset, 1)

    return int((N * (N + 1) / 2 + 1) / 2) <= sm

N = 0

def main():
    global N

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

    ok, ng = min(a), max(a) + 1

    while ok + 1 != ng:
        md = int((ok + ng) / 2)
        if check(a, md):
            ok = md
        else:
            ng = md


    print(ok)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = (int)(input())
l = (list)(map(int, input().split()))

cand = []
# naive way
for bef in range(n):
    for aft in range(bef+1, n+1):
        cand.append(l[bef:aft])
cand = list(map(lambda x: sorted(x), cand))
med_list = list(map(lambda x: x[len(x)//2], cand))
med_list = sorted(med_list)
print(med_list[len(med_list)//2])

Submission status: Time Limit Exceeded

Solution code:

from bisect import bisect_left
from math import ceil
# >= 3.3
# from collections.abc import Sequence
# < 3.3
from collections import Sequence


class LazySequence(Sequence):
    def __init__(self, f, n):
        self.f = f
        self.n = n

    def __len__(self):
        return self.n

    def __getitem__(self, i):
        if not (0 <= i < self.n):
            raise IndexError
        return self.f(i)


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

    def __len__(self):
        return self.size

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

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


N = int(input())
a = [0] + [int(s) for s in input().split()]


def count_lr(x):
    s = [0] * (N + 1)
    for i in range(1, N + 1):
        s[i] = s[i - 1] + (1 if a[i] >= x else -1)

    ss = sorted(s)

    def f(v):
        i = bisect_left(ss, v)
        return i + 1

    b = Bit(N + 10)
    count = 0
    for i in range(N + 1):
        fi = f(s[i])
        count += b.sum(fi)
        b.add(fi, 1)

    return count


# i: 0, 1, ..., 10 ** 9 + 10
# x: 10 ** 9 + 10, ..., 0
counts = LazySequence(lambda i: count_lr(10 ** 9 + 10 - i), 10 ** 9 + 10)
ans = 10 ** 9 + 10 - bisect_left(counts, ceil(N * (N + 1) / 4))
print(ans)

Submission status: Time Limit Exceeded

Solution code:

from bisect import bisect_left
from math import ceil
import collections.abc


class LazySequence(collections.abc.Sequence):
    def __init__(self, f, n):
        self.f = f
        self.n = n

    def __len__(self):
        return self.n

    def __getitem__(self, i):
        if not (0 <= i < self.n):
            raise IndexError
        return self.f(i)


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

    def __len__(self):
        return self.size

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

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


N = int(input())
a = [0] + [int(s) for s in input().split()]


def count_lr(x):
    s = [0] * (N + 1)
    for i in range(1, N + 1):
        s[i] = s[i - 1] + (1 if a[i] >= x else -1)

    ss = sorted(s)

    def f(v):
        i = bisect_left(ss, v)
        return i + 1

    b = Bit(N + 10)
    count = 0
    for i in range(N + 1):
        fi = f(s[i])
        count += b.sum(fi)
        b.add(fi, 1)

    return count


# i: 0, 1, ..., 10 ** 9 + 10
# x: 10 ** 9 + 10, ..., 0
counts = LazySequence(lambda i: count_lr(10 ** 9 + 10 - i), 10 ** 9 + 10)
ans = 10 ** 9 + 10 - bisect_left(counts, ceil(N * (N + 1) / 4))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
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)
ng, ok = 10 ** 9 + 1, 0
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))

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

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

print(ok)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools

def get_median(list_A):
    if len(list_A)==1:
        return int(list_A)
    elif len(list_A) <= 0:
        return False
    else:
        return int(sorted(np.array(list_A).reshape(-1,1))[int(len(list_A)/2)])

N = int(input())
a_list = np.array(list(map(int, input().split()))).reshape(-1,1)

if a_list.shape[0] <= 1:
    print(int(a_list))
    exit()
else:
    list_lr = list(itertools.combinations(range(N),2))
    all_a_sub_median = []

    for l,r in list_lr:
        a_sub = a_list[l:r]
        a_sub_median = get_median(a_sub)
        all_a_sub_median.append(a_sub_median)

    print(get_median(all_a_sub_median))

Submission status: Time Limit Exceeded

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

l = []
 
for i in range(n) :
    for j in range(0,n-i):
        t = []
        for k in range(i+1):
            #print(str(a[j+k])+ " ",end="")
            t.append(a[j+k])
        t.sort()
        l.append(t)
        #print()
m = []
for ll in l:
    m.append(ll[len(ll)//2])
m.sort()
#print(l)
#print(m)
print(m[len(m)//2])

Submission status: Time Limit Exceeded

Solution code:
N = int(input().rstrip())
num_list = [int(item) for item in input().split()]
search_list = sorted(num_list)

def fall_number(key):
  arr = []
  cusum = 0
  for item in num_list:
    cusum = cusum-1 if item < key else cusum+1
    arr.append(cusum)
  n_max, n_min = max(arr), min(arr)
  n = n_max - n_min + 1
  bit = [0] * n
  ans = 0
  for j, val in enumerate(arr):
    idx = val - n_min + 1
    _sum = 0
    while(idx > 0):
      _sum += bit[idx-1]
      idx -= (idx & -idx)
    idx = val - n_min + 1
    while(idx <= n):
      bit[idx-1] += 1
      idx += (idx & -idx)
    ans += j - _sum
  return ans

th = N*(N+1) / 4
right = len(search_list)
left = -1
while(right - left > 1):
  mid = (right + left) // 2
  if fall_number(search_list[mid]) >= th:
    right = mid
  else:
    left = mid
print(search_list[left])

Submission status: Time Limit Exceeded

Solution code:
N = int(input().rstrip())
num_list = [int(item) for item in input().split()]
search_list = sorted(list(set(num_list)))

def cusum(idx):
  tmp = []
  n = 0
  for item in num_list:
    n = n-1 if item < idx else n+1
    tmp.append(n)
  return tmp


def fall_number(key):
  def add(idx, val):
    while(idx <= n):
      bit[idx-1] += val
      idx += (idx & -idx)

  def calc(idx):
    res = 0
    while(idx > 0):
      res += bit[idx-1]
      idx -= (idx & -idx)
    return res
    
  arr = cusum(key)
  n_max, n_min = max(arr), min(arr)
  n = n_max - n_min + 1
  bit = [0] * n
  #BIT = binary_index_tree(n)
  ans = 0
  for val in arr:
    ans += calc(n) - calc(val - n_min + 1)
    add(val - n_min + 1, 1)
  #print(N * np.log2(N))
  return ans

def binary_serach(th):
  right = len(search_list)
  left = -1
  while(right - left > 1):
    mid = (right + left) // 2
    if fall_number(search_list[mid]) >= th:
      right = mid
    else:
      left = mid
  return left

th = N*(N+1) / 4 
res = binary_serach(th)

print(search_list[res])

Submission status: Time Limit Exceeded

Solution code:
N = int(input().rstrip())
num_list = [int(item) for item in input().split()]
num_sorted = sorted(num_list)

def cusum(idx):
  tmp = []
  n = 0
  for item in num_list:
    n = n-1 if item < idx else n+1
    tmp.append(n)
  return tmp

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

  def add(self, idx, val):
    while(idx <= self.n):
      self.bit[idx-1] += val
      idx = idx + (idx & -idx)

  def calc(self, idx):
    res = 0
    while(idx > 0):
      res += self.bit[idx-1]
      idx = idx - (idx & -idx)
    return res

def fall_number(idx):
  arr = cusum(idx)
  n_max, n_min = max(arr), min(arr)
  n = n_max - n_min + 1
  BIT = binary_index_tree(n)
  ans = 0
  for val in arr:
    ans += BIT.calc(n) - BIT.calc(val-n_min+1)
    BIT.add(val-n_min+1, 1)
  return ans

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

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())+1
ans=list(map(int,input().split()))
ar=ans[:]
for i in range(2,n):
    for e in range(0,n-i):
        a=ar[e:e+i]
        a.sort()
        ans.append(a[i>>1])
ans.sort()
print(int(ans[len(ans)>>1]))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())+1
import numpy as np
ans=list(map(int,input().split()))
ar=np.array(ans[:],dtype=np.int32)
for i in range(2,n):
    for e in range(0,n-i):
        ans.append(np.sort(ar[e:e+i])[i>>1])
print(int(sorted(ans)[len(ans)>>1]))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
import numpy as np
ans=list(map(int,input().split()))
ar=np.array(ans[:],dtype=np.int16)
for i in range(2,n+1):
    for e in range(0,n+1-i):
        ans.append(np.sort(ar[e:e+i])[i>>1])
print(int(sorted(ans)[len(ans)>>1]))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
import numpy as np
ar=np.array(list(map(int,input().split())),dtype=np.int32)
ans=list(ar[:])
for i in range(2,n+1):
    for e in range(0,n+1-i):
        ans.append(np.sort(ar[e:e+i])[i>>1])
print(int(sorted(ans)[len(ans)>>1]))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
import numpy as np
ar=np.array(list(map(int,input().split())),dtype=np.int32)
ans=ar[:]
for i in range(2,n+1):
    for e in range(0,n+1-i):
        ans=np.append(ans,np.sort(ar[e:e+i])[i>>1])
print(int(np.sort(ans)[ans.size>>1]))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
lst=list(map(int,input().split()))
ans=[]
for i in range(1,n+1):
    for e in range(0,n+1-i):
        ans.append(sorted(lst[e:e+i])[i//2])
print(sorted(ans)[len(ans)//2])

Submission status: Time Limit Exceeded

Solution code:
import itertools
n=int(input())
lst=list(map(int,input().split()))
ans=[]
for c in list(itertools.combinations(range(len(lst)+1),2)):
    ans.append(lst[c[0]:c[1]][(c[1]-c[0])//2])
print(sorted(ans)[len(ans)//2])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
import math
import numpy as np

d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


class BIT(object):
    """
    BITの実装

    Attention
    ---------
    添字は1始まり

    Prameters
    ---------
    a_list : list
        対象の配列

    Method
    ------
    add(i, x) : a_iにxを足す

    sum(i) : a_1 + a_2 + ... + a_i を返す

    Attributes
    ----------
    N : int
        bit配列の長さ, len(a_list)に等しい

    bit : list, shape = [N]
        BIT配列
    """
    def __init__(self, N):
        self.N = N
        self.bit = [0] * self.N

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

    def sum(self, i):
        """ a_1 + a_2 + ... + a_i """
        ret = 0
        while i > 0:
            ret += self.bit[i-1]
            i -= i & -i
        return ret


def calc_inversion_num(x, a_list):
    n_a = len(a_list)
    transformed = np.zeros(n_a)
    transformed[a_list < x] = -1
    transformed[transformed != -1] = 1

    cum_t = transformed.cumsum()
    filtered_t = np.unique(cum_t)
    bit = BIT(len(filtered_t))

    inv = (transformed == -1).sum()

    for i, c in enumerate(cum_t):
        idx = np.searchsorted(filtered_t, c)
        temp_inv = bit.sum(idx + 1)
        bit.add(idx + 1)
        inv += i - temp_inv

    return inv


N = d_in()
a_list = ds_in()

a_list = np.array(a_list)
sorted_a = np.sort(a_list)

search_range = [0, N]  # range [0, N)
while search_range[1] - search_range[0] > 1:
    mid = (search_range[0] + search_range[1]) // 2
    inv = calc_inversion_num(sorted_a[mid], a_list)
    if (N * (N+1) / 2 - inv) < math.ceil(N * (N+1) / 4):
        search_range[1] = mid
    else:
        search_range[0] = mid

print(sorted_a[search_range[0]])