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: Runtime Error

Solution code:
#!/usr/bin/env python3
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:
            bit.add(s + n, 1)
            ret += bit.sum(s + n - 1)
        return ret

    while lo < hi:
        mid = (lo + hi) // 2
        if th < _f(xs[mid]):
            lo = mid + 1
        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))  # type: int
    a = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    result = solve(N, a)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
a = list(map(int, input().split()))
total = 0
if N == 1:
    print(a[0])
    exit()
if N == 2:
    print(a[1])
    exit()
for i in range(1, N+1):
    total += i
index = total // 2 + 1
l = i
total1 = 0
for i in range(1, N+1)[::-1]:
    index -= i
    if index < 0:
        index += i
        break
print(sorted(a[index-1:index-1+l])[l//2+1])

Submission status: Runtime Error

Solution code:
import numpy as np

n = int(input())
lst = 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

            
def judge(x, lst):

    length = len(lst)
    all_pair = (length*(length-1) // 2) + length
    
    lst_r = [-1 if i < x else 1 for i in lst]
    lst_accum = []
    a = 0
    for i in lst_r:
        a += i
        lst_accum.append(a)
    min_a = min(lst_accum)
    lst_accum = [i - min_a + 1 for i in lst_accum]
    
    bit = Bit(max(lst_accum))
    ans = 0
    for i, p in enumerate(lst_accum):
        bit.add(p, 1)
        ans += i + 1 - bit.sum(p)
    
    ans = all_pair - ans
    if ans >= (all_pair//2) + 1:
        return True
    else:
        return False

    
lst = sorted(lst)
low = 0
high = len(lst) - 1
t = (low+high) // 2
while low < high:
    i = lst[t]
    if judge(i, lst):
        if low == t:
            break
        low = t
        t = (low+high) // 2
    else:
        if high == t:
            break
        high = t
        t = (low+high) // 2
        
print(lst[high]) if judge(lst[high], lst) else print(lst[low])

Submission status: Runtime Error

Solution code:
import numpy as np

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 judge(x, lst):

    length = len(lst)
    all_pair = (length*(length-1) // 2) + length
    
    lst_r = [-1 if i < x else 1 for i in lst]
    array = np.cumsum(np.array(lst_r))
    lst_accum = array - min(array) + 1
    
    bit = Bit(max(lst_accum))
    ans = 0
    for i, p in enumerate(lst_accum):
        bit.add(p, 1)
        ans += i + 1 - bit.sum(p)
    
    ans = all_pair - ans
    if ans >= (all_pair//2) + 1:
        return True
    else:
        return False

    
lst = sorted(lst)
low = 0
high = len(lst) - 1
t = (low+high) // 2
while low < high:
    i = lst[t]
    if judge(i, lst):
        if low == t:
            break
        low = t
        t = (low+high) // 2
    else:
        high = t
        t = (low+high) // 2
        
print(lst[high]) if judge(lst[high], lst) else print(lst[t])

Submission status: Runtime Error

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

    def __init__(self, size: int):
        """サイズを指定して BIT を初期化します。
        """
        # BIT のサイズは 2^n + 1
        self.__size = 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 inversion(A: list) -> int:
    bit = BIT(max(A))
    s = 0
    for a in A[1:]:
        bit.add(a, 1)
        s += bit.sum(0, a)

    return a


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

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

    return inversion(S[1:])


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 = [int(s) for s in input().split()]
    ans = median_of_medians(N, A)
    print(ans)

Submission status: Runtime Error

Solution code:
import statistics

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]
print(statistics.median_high(s))

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
median_len=N*(N+1)//2
median=median_len//2+1
a=1
medin_rank=1
for i in range(1,N):
    a=i*(i+1)//2
    b=(i+2)*(i+1)//2
    if a<=median and b>median:
        medin_rank=i
        break
rank_index=median-a
median_list=[]
l=medin_rank//2
for i in range(N-medin_rank+1):
    if (l+i)<N:
        median_list.append(A[l+i])
median_list.sort()
if rank_index<N:
    print(median_list[rank_index])
else:
    print(34)

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
median_len=N*(N+1)//2
median=median_len//2+1
a=1
medin_rank=1
for i in range(1,N):
    a=i*(i+1)//2
    b=(i+2)*(i+1)//2
    if a<=median and b>median:
        medin_rank=i
        break
rank_index=median-a
median_list=[]
l=medin_rank//2
for i in range(N-medin_rank+1):
    if (l+i)<N:
        median_list.append(A[l+i])
median_list.sort()
print(median_list[rank_index])

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
median_len=N*(N+1)//2
median=median_len//2+1
a=1
medin_rank=1
for i in range(1,N):
    a=i*(i+1)//2
    b=(i+2)*(i+1)//2
    if a<=median and b>median:
        medin_rank=i
        break
rank_index=median-a
median_list=[]
l=medin_rank//2
for i in range(N-medin_rank+1):
    if (l+i)<N:
        median_list.append(A[l+i])
print(median_list[rank_index])

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
median_len=N*(N+1)//2
median=median_len//2+1
a=1
medin_rank=1
for i in range(1,N):
    a=i*(i+1)//2
    b=(i+2)*(i+1)//2
    if a<=median and b>median:
        medin_rank=i
        break
rank_index=median-a
median_list=[]
l=medin_rank//2
for i in range(N-medin_rank+1):
    median_list.append(A[l+i])
print(median_list[rank_index])

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
median_len=N*(N+1)//2
median=median_len//2+1
a=0
medin_rank=1
for i in range(1,N):
    a=i*(i+1)//2
    b=(i+2)*(i+1)//2
    if a<=median and b>median:
        medin_rank=i
        break
rank_index=median-a
median_list=[]
l=medin_rank//2
for i in range(N-medin_rank+1):
    median_list.append(A[l+i])
print(median_list[rank_index])

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
median_len=N*(N+1)//2
median=median_len//2+1
a=0
medin_rank=1
for i in range(1,N):
    a=i*(i+1)//2
    b=(i+2)*(i+1)//2
    if a<=median and b>median:
        medin_rank=i
        break
rank_index=median-a-1
median_list=[]
l=medin_rank//2
for i in range(N-medin_rank+1):
    median_list.append(A[l+i])
print(median_list[rank_index])

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
median_len=N*(N+1)//2
median=median_len//2+1
for i in range(1,N):
    a=i*(i+1)//2
    b=(i+2)*(i+1)//2
    if a<=median and b>median:
        medin_rank=i
        break
rank_index=median-a-1
median_list=[]
l=medin_rank//2
for i in range(N-medin_rank+1):
    median_list.append(A[l+i])
print(median_list[rank_index])

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
median_len=N*(N+1)//2
median=median_len//2
for i in range(1,N):
    a=i*(i+1)//2
    b=(i+2)*(i+1)//2
    if a<=median and b>median:
        medin_rank=i
        break
rank_index=median-a
median_list=[]
l=medin_rank//2
for i in range(N-medin_rank+1):
    median_list.append(A[l+i])
print(median_list[rank_index])

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
median_len=N*(N+1)//2
median=median_len//2+1
for i in range(1,N+1):
    a=i*(i+1)//2
    b=(i+2)*(i+1)//2
    if a<=median and b>median:
        medin_rank=i
        break
rank_index=median-a
median_list=[]
l=medin_rank//2
for i in range(N-medin_rank+1):
    median_list.append(A[l+i])
print(median_list[rank_index])

Submission status: Runtime Error

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 = md1


    print(ok)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n = (int)(input())
l = (list)(map(int, input().split()))
sorted(l)
print(l[n//2+1])

Submission status: Runtime Error

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

if n == 1:
    print(a[0])
else :
    b = list(set(a))
    b.sort()
    print(b[len(b)//2+1])

Submission status: Runtime Error

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

if n == 1:
    print(a[0])
else :
    a.sort()
    b = list(set(a))
    print(b[len(b)//2+1])

Submission status: Runtime Error

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]
        ans.append(a.sort()[i>>1])
print(int(ans.sort()[len(ans)>>1]))

Submission status: Runtime Error

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):
        ans.append(ar[e:e+i].sort()[i>>1])
print(int(ans.sort()[len(ans)>>1]))

Submission status: Runtime Error

Solution code:
n=int(input())
import numpy as np
    ans=list(map(int,input().split())),dtype=np.int16)
ar=np.array((ans[:])
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: Runtime Error

Solution code:
N = int(input().rstrip())
num = [int(item) for item in input().split()]
new_m = []
for i in range(N):
  idx = (i+1) // 2
  new_m.extend([sorted(num[j:j+i+1])[idx] for j in range(N-i)])
new_m.sort()
print(new_m[N + N * N // 4])

Submission status: Runtime Error

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

Submission status: Runtime Error

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

if n == 1:
    print(a[0])
    exit()

b = list(sorted(set(a)))

def count_inversion(ans):
    s = [0 for _ in range(2 * n + 2) ]

    def bit_add(i):
        x = i
        while x < 2 * n:
            s[x] += 1
            x += x & -x

    def bit_sum(i):
        x = i
        ret = 0
        while x > 0:
            ret += s[x]
            x -= x & -x
        return ret

    temp = [n for _ in range(n + 1)]
    temp[0] = n + 1
    for i in range(n):
        if a[i] >= b[ans]:
            temp[i + 1] = temp[i] + 1
        else:
            temp[i + 1] = temp[i] - 1
    res = 0
    for i in range(n + 1):
        x = temp[i]
        res += bit_sum(x)
        bit_add(x)
    return res

m = n * (n + 1) // 2

ans = 0

l = 0
r = len(b)
while 1:
    ans = (l + r) // 2
    if count_inversion(ans) * 2 >= m:
        l = ans
    else:
        r = ans
    if r - l <= 1:
        ans = l
        break

print(b[ans])
n = int(input())
a = list(map(int, input().split()))

if n == 1:
    print(a[0])
    exit()

b = list(sorted(set(a)))

def count_inversion(ans):
    s = [0 for _ in range(2 * n + 2) ]

    def bit_add(i):
        x = i
        while x < 2 * n:
            s[x] += 1
            x += x & -x

    def bit_sum(i):
        x = i
        ret = 0
        while x > 0:
            ret += s[x]
            x -= x & -x
        return ret

    temp = [n for _ in range(n + 1)]
    temp[0] = n + 1
    for i in range(n):
        if a[i] >= b[ans]:
            temp[i + 1] = temp[i] + 1
        else:
            temp[i + 1] = temp[i] - 1
    res = 0
    for i in range(n + 1):
        x = temp[i]
        res += bit_sum(x)
        bit_add(x)
    return res

m = n * (n + 1) // 2

ans = 0

l = 0
r = len(b)
while 1:
    ans = (l + r) // 2
    if count_inversion(ans) * 2 >= m:
        l = ans
    else:
        r = ans
    if r - l <= 1:
        ans = l
        break

print(b[ans])

Submission status: Runtime Error

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

if n == 1:
    print(a[0])
    exit()

b = list(sorted(set(a)))

def count_inversion(ans):
    s = [0 for _ in range(2 * n) + 2]

    def bit_add(i):
        x = i
        while x < 2 * n:
            s[x] += 1
            x += x & -x

    def bit_sum(i):
        x = i
        ret = 0
        while x > 0:
            ret += s[x]
            x -= x & -x
        return ret

    temp = [n for _ in range(n + 1)]
    temp[0] = n + 1
    for i in range(n):
        if a[i] >= b[ans]:
            temp[i + 1] = temp[i] + 1
        else:
            temp[i + 1] = temp[i] - 1
    res = 0
    for i in range(n + 1):
        x = temp[i]
        res += bit_sum(x)
        bit_add(x)
    return res

m = n * (n + 1) // 2

ans = 0

l = 0
r = len(b)
while 1:
    ans = (l + r) // 2
    if count_inversion(ans) * 2 >= m:
        l = ans
    else:
        r = ans
    if r - l <= 1:
        ans = l
        break

print(b[ans])

Submission status: Runtime Error

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

if n == 1:
    print(a[0])
    exit()

b = list(sorted(set(a)))

def count_inversion(ans):
    s = [0 for _ in range(2 * n)]

    def bit_add(i):
        x = i
        while x < 2 * n:
            s[x] += 1
            x += x & -x

    def bit_sum(i):
        x = i
        ret = 0
        while x > 0:
            ret += s[x]
            x -= x & -x
        return ret

    temp = [n for _ in range(n + 1)]
    temp[0] = n + 1
    for i in range(n):
        if a[i] >= b[ans]:
            temp[i + 1] = temp[i] + 1
        else:
            temp[i + 1] = temp[i] - 1
    res = 0
    for i in range(n + 1):
        x = temp[i]
        res += bit_sum(x)
        bit_add(x)
    return res

m = n * (n + 1) // 2

ans = 0

l = 0
r = len(b)
while 1:
    ans = (l + r) // 2
    if count_inversion(ans) * 2 >= m:
        l = ans
    else:
        r = ans
    if r - l <= 1:
        ans = l
        break

print(b[ans])

Submission status: Runtime Error

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

b = list(sorted(set(a)))

def count_inversion(ans):
    s = [0 for _ in range(2 * n)]

    def bit_add(i):
        x = i
        while x < 2 * n:
            s[x] += 1
            x += x & -x

    def bit_sum(i):
        x = i
        ret = 0
        while x > 0:
            ret += s[x]
            x -= x & -x
        return ret

    temp = [n for _ in range(n + 1)]
    temp[0] = n + 1
    for i in range(n):
        if a[i] >= b[ans]:
            temp[i + 1] = temp[i] + 1
        else:
            temp[i + 1] = temp[i] - 1
    res = 0
    for i in range(n + 1):
        x = temp[i]
        res += bit_sum(x)
        bit_add(x)
    return res

m = n * (n + 1) // 2

ans = 0

l = 0
r = len(b)
while 1:
    ans = (l + r) // 2
    if count_inversion(ans) * 2 >= m:
        l = ans
    else:
        r = ans
    if r - l <= 1:
        ans = l
        break

print(b[ans])

Submission status: Runtime Error

Solution code:
N = int(input())
src = list(map(int,input().split()))

cands = list(sorted(set(src)))

def enough(i):
    bit = [0] * (2*N+10)
    def bit_add(a,w):
        x = a
        while x <= (2*N+9):
            bit[x] += w
            x += (x & -x)
    def bit_sum(a):
        x = a
        ret = 0
        while x > 0:
            ret += bit[x]
            x -= (x & -x)
        return ret

    cums = [0]
    for a in src:
        tmp = 1 if a >= cands(i) else -1
        cums.append(cums[-1] + tmp)

    cnt = 0
    for i in range(N+1):
        a = cums[i] + N+5
        cnt += bit_sum(a)
        bit_add(a, 1)
    return cnt*2 >= N*(N+1)//2

ok = 0
ng = len(cands)
while ng - ok > 1:
    m = (ok+ng)//2
    if enough(m):
        ok = m
    else:
        ng = m
print(ok)

Submission status: Runtime Error

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

def med(x):
  x.sort()
  return x[int(len(x)/2)]

b = []

for i in range(n-1):
  for j in range(i+1,n):
    b.append(med(a[i:j+1]))
  
print(med(b))

Submission status: Runtime Error

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

def med(x):
  x.sort()
  return int(len(x)/2)

b = []

for i in range(n-1):
  for j in range(i+1,n):
    b.append = med(a[i:j+1])
  
print(med(b))

Submission status: Runtime Error

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

def med(x):
  x.sort()
  return int(len(x)/2)
b = []

for i in range(n-1):
  for j in range(i+1,n):
    b.append = med(a[i:j+1])
  
print(med(b))

Submission status: Runtime Error

Solution code:
import math
N = int(input())

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

b = []

for i in range(1, math.ceil(N/2)+1):
    b.extend([a[i-1]] * (2*i - 1))

for i in range(math.ceil(N/2)+1, N+1):
    b.extend([a[i-1]] * ((N-i+1)*2))

b.sort()
print(b[math.ceil(len(b)/2)])

Submission status: Runtime Error

Solution code:
import math

def med(num_list):
    num_list.sort()
    return num_list[math.floor(len(num_list)/2)]

def main():
    N = int(input())

    a = list(map(int, input().split()))
    b = []

    for i in range(0, N):
        for j in range(i, N):
            b.append(med(a[i:j+1]))

    print(med(ba))

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
 encoding: utf-8
# import time
# t0 = time.time()

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

dict_count = {}
seq_list = []

# t1 = time.time()
# print("#", t1 - t0)

a_sort = sorted(a) # Nlog(N)
l = 0
r = N - 1
while l < r: # log(N)
    i_m = l + (r - l) // 2
    m = a_sort[i_m]
    a_comp = [2 * int(a[i] >= m) - 1 for i in range(N)] # N
    # accumulation
    acm_list = []
    acm = 0
    for i, ai_comp in enumerate(a_comp): # N
        acm += ai_comp
        acm_list.append(acm)
    # merge sort (divide)
    score = 0
    acm_list_temp = [[item] for item in acm_list]
    while len(acm_list_temp) > 1: # Nlog(N)
        pair = [None] * 2
        state = 0
        acm_list_temp2 = []
        for item in acm_list_temp:
            pair[state] = item
            if state == 0:
                state = 1
                continue
            # if state == 1
            newitem = []
            for i in range(len(pair[0]) + len(pair[1])):
                # count
                if pair[0][0] <= pair[1][0]:
                    newitem.append(pair[0].pop(0))                    
                    score += 1
                else:
                    newitem.append(pair[1].pop(0))
                    score -= 1
                # escape
                if len(pair[0]) < 1:
                    newitem += pair[1]
                    score += len(pair[1])
                    break
                elif len(pair[1]) < 1:
                    newitem += pair[0]
                    score -= len(pair[0])
                    break
                else: continue
            acm_list_temp2.append(newitem)
            state = 0
        else:
            if state == 1: acm_list_temp2.append(item)
        acm_list_temp = list(acm_list_temp2)
    # update l or r
    if score < 0: r = i_m - 1
    else: l = i_m
    
# ans
# t2 = time.time()
# print("#", t2 - t1)
if l == 0 and r == 0: print(a_sort[0])
else: print(m)

Submission status: Runtime Error

Solution code:
 encoding: utf-8
# import time
# t0 = time.time()

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

dict_count = {}
seq_list = []

# t1 = time.time()
# print("#", t1 - t0)

a_sort = sorted(a) # Nlog(N)
left = 0
right = N - 1
while True: # log(N)
    i_m = left + (right - left + 1) // 2
    m = a_sort[i_m]
    a_comp = [2 * int(a[i] >= m) - 1 for i in range(N)] # N
    sum_a = 0
    # sum whether sum(a_comp[l, r] >= 0) for all (l, r)
    for i, ai_comp in enumerate(a_comp): # N
        sum_a += ai_comp * (i + 1) * (N - i)
    # update left of right
    if sum_a < 0: right = i_m - 1
    else: left = i_m
    # escape
    if left == right: break

# ans
# t2 = time.time()
# print("#", t2 - t1)
print(m)

Submission status: Runtime Error

Solution code:
_ = input()
line = list(map(int, input().split()))

t1 = a[len(a)//2]
t2 = sorted(a)[len(a)//2]
d = list()
for aa in a:
    if aa >= t1 and aa <= t2 or aa >= t2 and aa <= t1:
        d.append(aa)
sorted(d)[len(d)//2 - 1]

Submission status: Runtime Error

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

N = int(input())
a = list(map(int, input().split()))
med_list= []
for i in range(N):
    for j in range(i + 1, N + 1):
        med_list.append(median(a[i:j]))

b = []
for i in range(N):
    b += [a[i]] * ((i) * (N - i))
print(median(b))

Submission status: Runtime Error

Solution code:
n=int(input())
c=0
g=0
bg=0
hk=sum([i for i in range(1,n+1)])//2+1
#print(hk,"hk")
while c<n:
   g+=n-c
   #print(g)
   c+=1
   if g>=hk:
      z=hk-bg+2
      #q=[z-1,z+c-2]
      q=list(map(int,input().split()))[z-1:z+c-1]
      print(sorted(q)[len(q)//2])
      #print(q)
      break
   bg=g

Submission status: Runtime Error

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

a.sort()
mid = (N * (N + 1) / 2) // 2

num = 0
move = 0
while 1:
    num += 1
    move += (num * (num + 1) / 2)
    if move >= mid:
        break

print(a[num])

Submission status: Runtime Error

Solution code:
import statistics
n = int(input())
a = list(map(int,input().split()))
p = int(int(n *(n+1)/2)/2 + 1)
ans = a
flg = False
j = 2
for i in range(2,n):
  if(i+j >= n):
    break
  t = statistics.median_high(a[j:i+j])
  ans.append(t)
   if(ans.count(t) >= p):
    break
  j = j * j
print(statistics.median_high(ans))

Submission status: Runtime Error

Solution code:
import statistics
n=int(input())
a=map(int,input().split())
b=[]

for i in  range(n):
    for j in range(i+1):
        b.append(statistics.median(a[j:i]))

print(statistics.median(b))

Submission status: Runtime Error

Solution code:
import statistics

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

l = []

if len(a) > 10**4:
    a = a[len(a)/2-5*10**3:len(a)/2+5*10**3]

for i in range(len(a)):
    for j in range(i,len(a)):
        l.append(statistics.median_high(a[i:j+1]))

print(statistics.median_high(l))

Submission status: Runtime Error

Solution code:
# N, K = 9, 5
# X = [int(i) for i in '-9 -7 -4 -3 0 1 2 3 4'.split()]
N, K = map(int, input().split())
X = [int(i) for i in input().split()]
X_plus = []
X_minus = []
for i in range(N):
    if X[i] < 0:
        X_minus.append(X[i])
    else:
        X_plus.append(X[i])
# print(X_plus)
# print(X_minus)
res = []
len_plus = len(X_plus)
len_minus = len(X_minus)
if len_minus != 0:
    for i_plus in range(len_plus):
        if K-i_plus-1 <= len_minus:
            res.append(X_plus[i_plus]*2 - X_minus[-(K-i_plus-1)])
if len_plus >= K:
    res.append(X_plus[K-1])
 
if len_plus != 0:
    for i_minus in range(len_minus):
        if K-i_minus <= len_plus:
            res.append(abs(-X_minus[-i_minus-1])*2 + X_plus[K-i_minus-2])
if len_minus >= K:
    if len_plus > 0:
        if X_plus[0]==0:
            res.append(-X_minus[-K+1])
    else:
        res.append(-X_minus[-K])
print(min(res))

Submission status: Runtime Error

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

a.sort()
print(a[n//2 + 1])

Submission status: Runtime Error

Solution code:
# coding: utf-8

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

for i in range(n):
    for j in range(i + 1, n):
        m.append(sorted(a[i:j])[(j - i) // 2])

print(sorted(m)[len(m) // 2])

Submission status: Runtime Error

Solution code:
import statistics
n=int(input())
a=list(int(i) for i in input().split())
l=[]
for i in range(n,0,-1):
    for j in range(0,i):
        b=a[j:i]
        b.sort()
        c=i-j
        if c%2==0:
            d=int(c/2)
            m=b[d]
        else:
            m= statistics.median(b)
        l.append(m)
l.sort()
x=len(l)
if x%2==0:
    y=int(x/2)
    z=l[y]
else:
    z= statistics.median(x)
print(z)

Submission status: Runtime Error

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

print(a[N // 2])

Submission status: Runtime Error

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

print(a[N //2])

Submission status: Runtime Error

Solution code:
n = int(input())
a_list = sorted([int(i) for i in input().split()])

med_idx = n//2 + 1
print(a_list[med_idx])

Submission status: Runtime Error

Solution code:
# coding: utf-8

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

print(a[n // 2 + 1])

Submission status: Runtime Error

Solution code:
n=int(input())
a=input().split()
a=list(int(i) for i in a)
l=[]
for i in range(n,0,-1):
    for j in range(0,i):
#        print(j,i)
        b=a[j:i]
        print(b)
        b.sort()
        c=i-j
        if c%2==0:
            d=int(c/2)
            m=b[d]
        else:
            d=int((c-1)/2)
            m=b[d]
        l.append(m)
print(l)
l.sort()
x=len(l)
if x%2==0:
    y=int(x/2)
    z=l[y]
else:
    y=int((x-1)/2)
    z=l[y]
print(z)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
print(a[n // 2 + 1])

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
    print(a[n // 2 + 1])

Submission status: Runtime Error

Solution code:
N = int(raw_input())
a = map(int, raw_input())

print a[N / 2]

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
if n % 2 == 1:
    print(a[n // 2 + 1])
else:
    print(a[n * 2 // 3])

Submission status: Runtime Error

Solution code:
N = int(raw_input())
a = map(int, raw_input())

print a[N / 2 + 1]

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
if n % 2 == 1:
    print(a[n // 2 + 1])
else:
    print(a[n * 3 // 4 - 1])