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: Accepted

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

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

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

Submission status: Accepted

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

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

        def sum(self, index):
            # 1からindexまでの和を計算
            ret = 0
            x = index
            while x > 0:
                ret += self.tree[x]
                x -= x & (-x)
            return ret

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

    def pair(x):
        a_prime = [-1] * N
        for k in range(N):
            if A[k] >= x:
                a_prime[k] = 1  # x未満か否かを{-1, 1}に圧縮

        s = [0]
        min_s = 0
        max_s = 0
        tmp = 0
        # 累積和と最小値, 最大値を同時に計算
        for a in a_prime:
            tmp += a
            min_s = min(min_s, tmp)
            max_s = max(max_s, tmp)
            s.append(tmp)

        bit_size = max_s - min_s + 1  # BITのサイズ
        bit = BIT(bit_size)
        ans = 0
        for sk in s:
            sk -= (min_s - 1)  # sの最小値を1に調整
            ans += bit.sum(sk)
            bit.add(sk, 1)
        return ans

    # l<=rとなる(l, r)の取り方について、その半分以上の値を返す最大の値が中央値
    border_median = (N * (N + 1) // 2 + 1) // 2
    ok = 0
    ng = 10**9 + 1  # 数列の要素の値の制約から、この値は中央値になりえない
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if pair(mid) >= border_median:
            ok = mid
        else:
            ng = mid
    ans = ok
    return ans

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

Submission status: Accepted

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

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

        def sum(self, index):
            # 1からindexまでの和を計算
            ret = 0
            x = index
            while x > 0:
                ret += self.tree[x]
                x -= x & (-x)
            return ret

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

    def pair(x):
        a_prime = [-1] * N
        for k in range(N):
            if A[k] >= x:
                a_prime[k] = 1  # x未満か否かを{-1, 1}に圧縮

        s = [0]
        min_s = 0
        max_s = 0
        tmp = 0
        # 累積和と最小値, 最大値を同時に計算
        for a in a_prime:
            tmp += a
            min_s = min(min_s, tmp)
            max_s = max(max_s, tmp)
            s.append(tmp)

        bit_size = max_s - min_s + 1  # BITのサイズ
        bit = BIT(bit_size)
        ans = 0
        for sk in s:
            sk -= (min_s - 1)  # sの最小値を1に調整
            ans += bit.sum(sk)
            bit.add(sk, 1)
        return ans

    # l<=rとなる(l, r)の取り方について、その半分以上の値を返す最大の値が中央値
    border_median = (N * (N + 1) // 2 + 1) // 2
    ok = 0
    ng = 10**9 + 3
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if pair(mid) >= border_median:
            ok = mid
        else:
            ng = mid
    ans = ok
    return ans

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

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

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

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

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

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

    mi = 0
    ma = 10**9+1

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

    return mi


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

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

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


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

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

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

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

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

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

Submission status: Accepted

Solution code:
# D

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

# binary search
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])

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

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

    if n == 1: return a[0]

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

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

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

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

    mi = 0
    ma = 10**9+1

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

    return mi


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

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

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


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

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

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

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

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

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

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input() )
M = input().split() 
M=[int(a) for a in M]
M=np.array(M)
medians=[]
if N<10**5 and max(M)<10**9:
    for v in itertools.combinations_with_replacement(range(N), 2):
            m=M[v[0]:v[1]+1]
            m=np.sort(m)
            mid=int(len(m)/2)
            medians.append(m[mid])
    medians=np.sort(np.array(medians))
    mid2=int(len(medians)/2)
    print(medians[mid2])

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input() )
M = input().split() 
M=[int(a) for a in M]
M=np.array(M)
medians=[]
if N<10**5 and max(M)<10**9:
    for v in itertools.combinations_with_replacement(range(N), 2):
            m=M[v[0]:v[1]+1]
            m=np.sort(m)
            mid=int(N/2)
            medians.append(m[mid])
    medians=np.sort(np.array(medians))
    mid2=int(len(medians)/2)
    print(medians[mid2])

Submission status: Runtime Error

Solution code:
N=int(input())
A=[int(c) for c in input().split()]
print(A[(N+1)//2]);

Submission status: Runtime Error

Solution code:
import math
import sys

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

sys.setrecursionlimit(10000)
b = list(set(a))
b.sort()
def nibutan(x):
  ok = 0
  ng = x
  while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if judge(b[mid]):
      ok = mid
    else:
      ng = mid
  return ok

def judge(x):
  v = [0] * (N + 1)
  for i in range(N):
    v[i + 1] = v[i] + (-1 if a[i] < x else 1)

  mi = min(v)
  ma = max(v)
  u = [0] * (N + 1)
  for i in range(N + 1):
    u[i] = v[i] - mi

  b = BIT(ma - mi + 1)
  Ans = 0
  for i in range(len(u)):
    Ans += b.get(0, u[i])
    b.add(u[i], 1)
  return Ans >= N * (N + 1) / 4

class BIT():
  def __init__(s, k):
    s.N = k
    s.L = math.ceil(math.log(s.N - 1) + 1)
    s.P = [1] * (s.L + 1)
    for i in range(1,s.L + 1):
      s.P[i] = s.P[i - 1] * 2
    s.K = s.P[-1] * 2
    s.T = [0] * s.K
    
  def get(s, l, r):
    return s.get_sub(l, r, 0, s.P[s.L] - 1, 0, 0)

  def get_sub(s, l, r, ml, mr, x, id):
    if ml >= l and r >= mr:
      return s.T[s.P[x] + id]
    if mr < l or r < ml:
      return 0
    Ans = s.get_sub(l, r, ml, (mr + ml - 1) // 2, x + 1, id * 2)
    Ans += s.get_sub(l, r, (mr + ml + 1) // 2, mr, x + 1, id * 2 + 1)
    return Ans

  def add(s, n, p):
    s.add_sub(n, p, s.L)

  def add_sub(s, n, p, x):
    s.T[s.P[x] + n] += p
    if x != 0:
      s.add_sub(n // 2, p, x - 1)

print(b[nibutan(len(b))])

Submission status: Runtime Error

Solution code:
import math

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

b = list(set(a))
b.sort()
def nibutan(x):
  ok = 0
  ng = x
  while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if judge(b[mid]):
      ok = mid
    else:
      ng = mid
  return ok

def judge(x):
  v = [0] * (N + 1)
  for i in range(N):
    v[i + 1] = v[i] + (-1 if a[i] < x else 1)

  mi = min(v)
  ma = max(v)
  u = [0] * (N + 1)
  for i in range(N + 1):
    u[i] = v[i] - mi

  b = BIT(ma - mi + 1)
  Ans = 0
  for i in range(len(u)):
    Ans += b.get(0, u[i])
    b.add(u[i], 1)
  return Ans >= N * (N + 1) / 4

class BIT():
  def __init__(s, k):
    s.N = k
    s.L = math.ceil(math.log(s.N - 1) + 1)
    s.P = [1] * (s.L + 1)
    for i in range(1, (s.L + 1)):
      s.P[i] = s.P[i - 1] * 2
    s.K = s.P[-1] * 2
    s.T = [0] * s.K
    
  def get(s, l, r):
    return s.get_sub(l, r, 0, s.P[s.L] - 1, 0, 0)

  def get_sub(s, l, r, ml, mr, x, id):
    if ml >= l and r >= mr:
      return s.T[s.P[x] + id]
    if mr < l or r < ml:
      return 0
    Ans = s.get_sub(l, r, ml, (mr + ml - 1) // 2, x + 1, id * 2)
    Ans += s.get_sub(l, r, (mr + ml + 1) // 2, mr, x + 1, id * 2 + 1)
    return Ans

  def add(s, n, p):
    s.add_sub(n, p, s.L)

  def add_sub(s, n, p, x):
    s.T[s.P[x] + n] += p
    if x != 0:
      s.add_sub(n // 2, p, x - 1)

print(b[nibutan(len(b))])

Submission status: Runtime Error

Solution code:
import math

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

b = list(set(a))
b.sort()
def nibutan(x):
  ok = 0
  ng = x
  while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if judge(b[mid]):
      ok = mid
    else:
      ng = mid
  return ok

def judge(x):
  v = [0] * (N + 1)
  for i in range(N):
    v[i + 1] = v[i] + (-1 if a[i] < x else 1)

  mi = min(v)
  ma = max(v)
  u = [0] * (N + 1)
  for i in range(N + 1):
    u[i] = v[i] - mi

  b = BIT(ma - mi + 1)
  Ans = 0
  for i in range(len(u)):
    Ans += b.get(0, u[i])
    b.add(u[i], 1)
  return Ans >= N * (N + 1) / 4

class BIT():
  def __init__(s, k):
    s.N = k
    s.L = math.ceil(math.log(N) + 1)
    s.P = [1] * (s.L + 1)
    for i in range(1, (s.L + 1)):
      s.P[i] = s.P[i - 1] * 2
    s.K = s.P[-1] * 2
    s.T = [0] * s.K
    
  def get(s, l, r):
    return s.get_sub(l, r, 0, s.P[s.L - 1] - 1, 0, 0)

  def get_sub(s, l, r, ml, mr, x, id):
    if ml >= l and r >= mr:
      return s.T[s.P[x] + id]
    if mr < l or r < ml:
      return 0
    Ans = s.get_sub(l, r, ml, (mr + ml - 1) // 2, x + 1, id * 2)
    Ans += s.get_sub(l, r, (mr + ml + 1) // 2, mr, x + 1, id * 2 + 1)
    return Ans

  def add(s, n, p):
    s.add_sub(n, p, s.L - 1)

  def add_sub(s, n, p, x):
    s.T[s.P[x] + n] += p
    if x != 0:
      s.add_sub(n // 2, p, x - 1)

print(b[nibutan(len(b))])

Submission status: Runtime Error

Solution code:
import itertools
N = int(input())
A = [int(_) for _ in input().split()]


class BinaryIndexedTree:
    """
        Parameters
        ----------
        array : list
            to construct BIT from
        f : func
            binary operation of the abelian group
        fi : func
            inverse mapping of f
            i.e. f(a, b) == c <-> fi(c, a) == b
        e : 
            identity element of the abelian group
        size : int
            limit for array size
    """

    def __init__(self, array, f, fi, e, size):
        self.f = f
        self.fi = fi
        self.e = e
        self.size = size
        self.n = len(array)
        self.dat = [e] * (size + 1)
        self.array = [e] * size
        self.build(array)

    def build(self, array_):
        for i, v in enumerate(array_):
            self.modify(i, v)

    def modify(self, p, v):
        """
        set value at position p (0-indexed)
        """
        fi, dat, f, size, array = self.fi, self.dat, self.f, self.size, self.array
        dv = fi(v, array[p])
        array[p] = v
        p += 1
        while p <= size:
            dat[p] = f(dat[p], dv)
            p += p & -p

    def query(self, l, r):
        """
        result on interval [l, r) (0-indexed)
        """
        return self.fi(self._query(r), self._query(l))

    def _query(self, p):
        dat, f, res = self.dat, self.f, self.e
        while p:
            res = f(res, dat[p])
            p -= p & -p
        return res


e = 0
size = 2 * N + 2
f = lambda a, b: a + b
fi = lambda c, a: c - a
offset = N


def check(x):
    cumsum = list(itertools.accumulate([0] + [1 if a <= x else -1 for a in A]))
    # sum([l:r)) = cumsum[r] - cumsum[l] >= 0
    # ⇔ cumsum[l] <= cumsum[r]
    BIT = BinaryIndexedTree([e] * size, f=f, fi=fi, e=e, size=size)
    count = 0
    for c in cumsum:
        c += offset
        count += BIT.query(0, c + 1)
        BIT.modify(c + 1, BIT.query(c + 1, c + 2) + 1)
    return 2 * count > N * (N + 1) // 2


A_sorted = [0] + sorted(set(A)) + [10**10]
lb = 0
rb = N + 1
# check(x) == Trueとなる最小のx
while rb - lb > 1:
    mid = (rb + lb) // 2
    if check(A_sorted[mid]):
        rb = mid
    else:
        lb = mid
print(rb)

Submission status: Runtime Error

Solution code:
N=int(input())
alist=list(map(int,input().split()))
numdict=[]
amount=0
if len(alist)==1:
  print(alist[0])
  exit()
i=1
for x in range(0,((N+1)//2)):
  numdict.append([alist[x],i])
  amount+=i
  i+=2
i=2
for x in range(N-1,((N+1)//2)-1,-1):
  numdict.append([alist[x],i])
  amount+=i
  i+=2

numdict.sort()

b=(amount//2)+1
c=0

for x in range(0,N):
  c+=numdict[x][1]
  if c>=b:
    break

print(numdict[x+1][0])

Submission status: Runtime Error

Solution code:
import numpy

class BinaryIndexedTree:
	# 0-index
	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 sum_btw(i, j):
		return self.sum(j) - self.sum(i - 1)
 
	def add(self, i, x):
		while i <= self.size:
			self.bit[i] += x
			i += (i & -i)

def main():
	n = int(input())
	a_list = list(map(int, input().split()))

	a_list_sorted = sorted(a_list)
	ub = n
	lb = 0
	th = (n * (n + 1) / 2 + 1) // 2

	while ub - lb > 1:		
		mid = (ub + lb) // 2
		mid_num = a_list_sorted[mid]

		bit = BinaryIndexedTree(2 * n + 2)
		result = 0
		tmp_sum = 0
		for i in range(n):
			if a_list[i] >= mid_num:
				tmp_sum += 1
			else:
				tmp_sum -= 1
			result += bit.sum(tmp_sum + n)
			bit.add(tmp_sum + n, 1)

		print(mid, result)
		if result >= th:
			lb = mid
		else:
			ub = mid
	print(mid_num)
	

if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
N = int(input())
a = list(map(int,input().split(" ")))
b = sorted(a)
m = b[N//2]
lst = []

dic = {}
def dfs(l,r,mid):
    dic[(l,r)] = 1
    lst.append(mid)

    if l == r:
        return

    if (r - l + 1) % 2 == 0:
        if a[r] < mid:
            if not (l,r-1) in dic:
                dfs(l,r-1,mid)
        else:
            if not (l,r-1) in dic:
                c = sorted(a[l:r])
                mid_ = c[(len(c)//2)]
                dfs(l,r-1,mid_)

        if a[l] < mid:
            if not (l+1,r) in dic:
                dfs(l+1,r,mid)

        elif not (l+1,r) in dic:
            c = sorted(a[l+1:r+1])
            mid_ = c[(len(c)//2)]
            dfs(l+1,r,mid_)
    else:
        if a[r] > mid:
            if not (l,r-1) in dic:
                dfs(l,r-1,mid)
        else:
            if not (l,r-1) in dic:
                c = sorted(a[l:r])
                mid_ = c[len(c)//2]
                dfs(l,r-1,mid_)

        if a[l] > mid:
            if not (l+1,r) in dic:
                dfs(l+1,r,mid)

        else:
            if not (l+1,r) in dic:
                c = sorted(a[l+1:r+1])
                mid_ = c[(len(c)//2)]
                dfs(l+1,r,mid_)

dfs(0,N-1,m)
lst.sort()
l = len(lst)
print(lst[(l//2)])

Submission status: Runtime Error

Solution code:
N = int(input())
a = list(map(int,input().split(" ")))
b = sorted(a)
m = b[N//2]
lst = []

dic = {}
def dfs(l,r,mid):
    if (l,r) in dic:
        return
    else:
        dic[(l,r)] = 1
        lst.append(mid)

    if l == r:
        return

    if (r - l + 1) % 2 == 0:
        if a[r] < mid:
            dfs(l,r-1,mid)
        else:
            c = sorted(a[l:r])
            mid_ = c[(len(c)//2)]
            dfs(l,r-1,mid_)

        if a[l] < mid:
            dfs(l+1,r,mid)

        else:
            c = sorted(a[l+1:r+1])
            mid_ = c[(len(c)//2)]
            dfs(l+1,r,mid_)
    else:
        if a[r] > mid:
            dfs(l,r-1,mid)
        else:
            c = sorted(a[l:r])
            mid_ = c[len(c)//2]
            dfs(l,r-1,mid_)

        if a[l] > mid:
            dfs(l+1,r,mid)

        else:
            c = sorted(a[l+1:r+1])
            mid_ = c[(len(c)//2)]
            dfs(l+1,r,mid_)

dfs(0,N-1,m)
lst.sort()
l = len(lst)
print(lst[(l//2)])

Submission status: Runtime Error

Solution code:
i=int(input())*2//3
s=input().split()
l=[]
for c in s:
    l.append(int(c))
l.sort()
print(l[i-2])

Submission status: Runtime Error

Solution code:
i=int(input())*2//3
s=input().split()
l=[]
for c in s:
    l.append(int(c))
l.sort()
print(l[i+2])

Submission status: Runtime Error

Solution code:
i=int(input())*2//3
s=input().split()
l=[]
for c in s:
    l.append(int(c))
l.sort()
print(l[i+1])

Submission status: Runtime Error

Solution code:
import sys
n = int(input())
a = list(map(int, sys.stdin.readline().split()))
def median_of_medians(A, i):

    #divide A into sublists of len 5
    sublists = [A[j:j+5] for j in range(0, len(A), 5)]
    medians = [sorted(sublist)[len(sublist)/2] for sublist in sublists]
    if len(medians) <= 5:
        pivot = sorted(medians)[len(medians)/2]
    else:
        #the pivot is the median of the medians
        pivot = median_of_medians(medians, len(medians)/2)

    #partitioning step
    low = [j for j in A if j < pivot]
    high = [j for j in A if j > pivot]

    k = len(low)
    if i < k:
        return median_of_medians(low,i)
    elif i > k:
        return median_of_medians(high,i-k-1)
    else: #pivot = k
        return pivot

print median_of_medians(a, n//2+1)

Submission status: Runtime Error

Solution code:
n = (int(input())
x = [int(i) for i in input().split()]
x = sorted(x)
if n==1: print(x[0])
elif n==2: print(x[1])
elif n%2==1: print(x[(n+1)//2])
else: print(x[n//2+1])

Submission status: Runtime Error

Solution code:
import sys
def select(A, i): # A is a list, i is the ith element in that ordered list
                  # NOTE all elements must be unique
    T = list(A)
    if len(A) <= 5: # Base case, just find ith element
        T = list(A)
        T.sort()
        return T[i]
    p = median_of_medians(A)
    (A_l, A_r, i_p) = partition(A, p)
    if i_p == i:
        return p
    elif i_p < i:
        return select(A_r, i - i_p - 1)    
    else: # i_p > i
        return select(A_l, i)
    
def median_of_medians(A):
    B = list()                # B will hold medians of sublists
    itrs, i = len(A)/5, 0
    for j in range(itrs): # divide list into sublists of len 5
        sub_list = A[i:i+5]  
        m = median(sub_list)
        B.append(m)
        i += 5
    end = len(A) % 5 
    if end != 0:
        B.append(median(A[-end:])) # add the last group to the pot
    p = select(B, len(B)/2)
    return p

def partition(A, p): # splits the list into left and right half where
                     # everything less is in the left list
    (A_l, A_r, i_p) = [], [], 0
    for elem in A:
        if p > elem:
            A_l.append(elem)
        elif p < elem:
            A_r.append(elem)
    i_p = len(A_l)
    return A_l, A_r, i_p


def median(A):  # A cheat to find the median in our base case
    T = list(A) # copies list!
    T.sort()
    i = len(T)/2 #  in list of 4 selects the 3rd element
    return T[int(i)]
    
def proof(A, i): # naive impl of select to justify correctness
    A = list(A)
    A.sort()
    print A[i]


n = int(input())
a = list(map(int, sys.stdin.readline().split()))
pivot = median_of_medians(a)
print (pivot)

Submission status: Runtime Error

Solution code:
def fun(tup):
    temp = sorted(tup)
    med = int(len(temp)/2)
    return temp[med]

N = int(input())
aa = []
aa = list(map(int, input().split()))
way = []
for i in range(N):
    for l in range(N):
        l=i+l
        if l == N:
            break
        if aa[i:l] != []:
            way.append(tuple(aa[i:l]))
way = list(set(way))
cc = list(map(fun,way))
cc = sorted(cc)
med = cc[int(len(cc)/2)]
print(med)

Submission status: Runtime Error

Solution code:
import sys
def select(A, i): # A is a list, i is the ith element in that ordered list
                  # NOTE all elements must be unique
    T = list(A)
    if len(A) <= 5: # Base case, just find ith element
        T = list(A)
        T.sort()
        return T[i]
    p = median_of_medians(A)
    (A_l, A_r, i_p) = partition(A, p)
    if i_p == i:
        return p
    elif i_p < i:
        return select(A_r, i - i_p - 1)    
    else: # i_p > i
        return select(A_l, i)
    
def median_of_medians(A):
    B = list()                # B will hold medians of sublists
    itrs, i = len(A)//5, 0
    for j in range(itrs): # divide list into sublists of len 5
        sub_list = A[i:i+5]  
        m = median(sub_list)
        B.append(m)
        i += 5
    end = len(A) % 5 
    if end != 0:
        B.append(median(A[-end:])) # add the last group to the pot
    p = select(B, len(B)//2)
    return p

def partition(A, p): # splits the list into left and right half where
                     # everything less is in the left list
    (A_l, A_r, i_p) = [], [], 0
    for elem in A:
        if p > elem:
            A_l.append(elem)
        elif p < elem:
            A_r.append(elem)
    i_p = len(A_l)
    return A_l, A_r, i_p


def median(A):  # A cheat to find the median in our base case
    T = list(A) # copies list!
    T.sort()
    i = len(T)/2 #  in list of 4 selects the 3rd element
    return T[int(i)]
    


n = int(input())
a = list(map(int, sys.stdin.readline().split()))
pivot = median_of_medians(a)
print (pivot)

Submission status: Runtime Error

Solution code:
import sys
def median_of_medians(A, i):

    #divide A into sublists of len 5
    sublists = [A[j:j+5] for j in range(0, len(A), 5)]
    medians = [sorted(sublist)[len(sublist)//2] for sublist in sublists]
    if len(medians) <= 5:
        pivot = sorted(medians)[len(medians)//2]
    else:
        #the pivot is the median of the medians
        pivot = median_of_medians(medians, len(medians)//2)

    #partitioning step
    low = [j for j in A if j < pivot]
    high = [j for j in A if j > pivot]

    k = len(low)
    if i < k:
        return median_of_medians(low,i)
    elif i > k:
        return median_of_medians(high,i-k-1)
    else: #pivot = k
        return pivot

n = int(input())
a = list(map(int, sys.stdin.readline().split()))
if n ==  1:
  print(a[0])
elif n == 2:
  a.sort()
  print(a[-1])
else:
  print (median_of_medians(a, n//2+1))

Submission status: Runtime Error

Solution code:
from bisect import bisect_left

n, k = map(int, input().split())
x = list(map(int, input().split()))
pos = bisect_left(x, 0)
#print(bisect_left(x, 0))

if x[0] >= 0:
	print(x[k - 1])
elif x[-1] <= 0:
	print(-x[-k])
else:
	ans = float("inf")
	if pos + k <= n:
		ans = x[pos + k - 1]
	if x[pos] == 0:
		if pos - k - 1 >= 0:
			ans = min(ans, -x[pos - k - 1])
	else:
		if pos - k >= 0:
			ans = min(ans, -x[pos - k])
	for i in range(max(pos, k - 1 - pos), min(pos + k - 1, n)):
		#print(i)
		right = x[i]
		left = -x[pos - (k - (i - pos + 1))]
		#print(right, left)
		ans = min(ans, 2 * right + left, 2 * left + right)

	print(ans)