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: Wrong Answer

Solution code:
from itertools import accumulate
def add(B,a,n):#リストに値を追加する関数
    x = a
    while x <= n:
        B[x] += 1
        x += x&(-x)

def sums(B,a):#a番目までの和
    x = a
    S = 0
    while x != 0:
        S += B[x]
        x -= x&(-x)
    return S


def invnumber(n, S):# #{(i,j)| i<j and S[i]<=S[j]}
    B = [0]*(n*2 + 1)
    invs = 0
    for i in range(n):
        s = S[i] + n
        invs += sums(B, s)
        add(B, s, n*2)
    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 = (R+L)//2
    S = [0]*N
    if A[0] >= M:
        S[0] = 1
    else:
        S[0] = -1
    for i in range(1,N):
        if A[i] >= M:
            S[i] = S[i-1] + 1
        else:
            S[i] = S[i-1] - 1
    if invnumber(N,S) >= c:
        L = M
    else:
        R = M
print(L)

Submission status: Wrong Answer

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準備
BIT = BinaryIndexedTree(N)
# 答えをにぶたん
lo, hi = -1, max(A) + 1  # sample2などに対応するためにhiを設定
while hi - lo > 1:
    m = (hi + lo) // 2

    # m以上かどうかで分類
    binary = [(1 if a >= m else -1) for a in A]
    binary = list(accumulate(binary))

    # BITの初期化
    BIT.reset()

    # 和が0以上となる連続部分列を数える
    tmp = 0

    # 転倒数っぽくやる
    binary_sorted = {b: i for i, b in enumerate(sorted(binary), start=1)}
    ans = 0
    for j, b in enumerate(binary):
        tmp += BIT.sum(binary_sorted[b]) + (binary_sorted[b] >= 0)
        BIT.add(binary_sorted[b], 1)

    # 連続する部分列の個数の半分以上和が0以上となる区間が存在するかで場合分け
    if tmp >= ceil(((N * (N + 1)) / 2) / 2):
        lo = m
    else:
        hi = m

print(lo)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
from math import ceil

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

if N == 1:
    print(A[0])
    exit()


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)  # Binaryの先頭の分
lo, hi = min(A) - 1, max(A) + 1
while hi - lo > 1:
    # Xは中央値候補
    X = (hi + lo) // 2

    # X以上なら1、X未満なら-1に変換
    Binary = [(1 if a >= X else -1) for a in A]

    # 累積和をとる
    Binary = list(accumulate(Binary))

    # BITを初期化
    BIT.reset()

    # 転倒数を数える
    inversion = 0
    Binary_sorted = {b: i for i, b in enumerate(sorted(Binary), start=1)}
    for j, b in enumerate(Binary):
        inversion += j - BIT.sum(Binary_sorted[b])
        BIT.add(Binary_sorted[b], 1)

    inversion = (N * (N + 1)) / 2 - inversion
    if inversion >= ceil((N * (N + 1) / 2) / 2):
        lo = X
    else:
        hi = X

print(lo)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

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

if N == 1:
    print(A[0])
    exit()


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)  # Binaryの先頭の分
lo, hi = min(A) - 1, max(A) + 1
while hi - lo > 1:
    # Xは中央値候補
    X = (hi + lo) // 2

    # X以上なら1、X未満なら-1に変換
    Binary = [(1 if a >= X else -1) for a in A]

    # 累積和をとる
    Binary = list(accumulate(Binary))

    # BITを初期化
    BIT.reset()

    # 転倒数を数える
    inversion = 0
    Binary_sorted = {b: i for i, b in enumerate(sorted(Binary), start=1)}
    for j, b in enumerate(Binary):
        inversion += j - BIT.sum(Binary_sorted[b])
        BIT.add(Binary_sorted[b], 1)

    inversion = (N * (N + 1)) / 2 - inversion
    if inversion >= (N * (N + 1) / 2) // 2:
        lo = X
    else:
        hi = X

print(lo)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

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

if N == 1:
    print(A[0])
    exit()


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)  # Binaryの先頭の分
lo, hi = min(A) - 1, 10 ** 9 + 1
while hi - lo > 1:
    # Xは中央値候補
    X = (hi + lo) // 2

    # X以上なら1、X未満なら-1に変換
    Binary = [(1 if a >= X else -1) for a in A]

    # 累積和をとる
    Binary = list(accumulate(Binary))

    # BITを初期化
    BIT.reset()

    # 転倒数を数える
    inversion = 0
    Binary_sorted = {b: i for i, b in enumerate(sorted(Binary), start=1)}
    for j, b in enumerate(Binary):
        inversion += j - BIT.sum(Binary_sorted[b])
        BIT.add(Binary_sorted[b], 1)

    # 転倒数の割合で分岐
    if inversion / (N * (N + 1) / 2) < 0.5:
        lo = X
    else:
        hi = X

print(lo)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

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)  # Binaryの先頭の分
lo, hi = min(A), max(A) + 1
while hi - lo > 1:
    # Xは中央値候補
    X = (hi + lo) // 2

    # X以上なら1、X未満なら-1に変換
    Binary = [(1 if a >= X else -1) for a in A]

    # 累積和をとる
    Binary = list(accumulate(Binary))

    # BITを初期化
    BIT.reset()

    # 転倒数を数える
    inversion = 0
    Binary_sorted = {b: i for i, b in enumerate(sorted(Binary), start=1)}
    for j, b in enumerate(Binary):
        inversion += j - BIT.sum(Binary_sorted[b])
        BIT.add(Binary_sorted[b], 1)

    # 転倒数の割合で分岐
    if inversion / (N * (N + 1) / 2) <= 0.5:
        lo = X
    else:
        hi = X

print(lo)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

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)  # Binaryの先頭の分
lo, hi = 0, max(A) + 1
while hi - lo > 1:
    # Xは中央値候補
    X = (hi + lo) // 2

    # X以上なら1、X未満なら-1に変換
    Binary = [(1 if a >= X else -1) for a in A]

    # 累積和をとる
    Binary = list(accumulate(Binary))

    # BITを初期化
    BIT.reset()

    # 転倒数を数える
    inversion = 0
    Binary_sorted = {b: i for i, b in enumerate(sorted(Binary), start=1)}
    for j, b in enumerate(Binary):
        inversion += j - BIT.sum(Binary_sorted[b])
        BIT.add(Binary_sorted[b], 1)

    # 転倒数の割合で分岐
    if inversion / (N * (N + 1) / 2) <= 0.5:
        lo = X
    else:
        hi = X

print(lo)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

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)  # Binaryの先頭の分
lo, hi = -1, max(A) + 1
while hi - lo > 1:
    # Xは中央値候補
    X = (hi + lo) // 2

    # X以上なら1、X未満なら-1に変換
    Binary = [(1 if a >= X else -1) for a in A]

    # 累積和をとる
    Binary = list(accumulate(Binary))

    # BITを初期化
    BIT.reset()

    # 転倒数を数える
    inversion = 0
    Binary_sorted = {b: i for i, b in enumerate(sorted(Binary), start=1)}
    for j, b in enumerate(Binary):
        inversion += j - BIT.sum(Binary_sorted[b])
        BIT.add(Binary_sorted[b], 1)

    # 転倒数の割合で分岐
    if inversion / (N * (N + 1) / 2) < 0.5:
        lo = X
    else:
        hi = X

print(lo)

Submission status: Wrong Answer

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

def count_inversion(input_array):
    n = max(input_array)
    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):
        #print(i, s)
        x = i
        ret = 0
        while x > 0:
            ret += s[x]
            x -= x & -x
        #print("ret", ret)
        return ret

    res = 0
    for i in range(len(input_array)):
        x = input_array[i]
        res += i - bit_sum(x)
        bit_add(x)
    return res

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

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

ans = len(b) // 2

l = 0
r = len(b) - 1
while 1:
    s = [n for _ in range(n + 1)]
    s[0] = n
    for i in range(n):
        if a[i] >= b[ans]:
            s[i + 1] = s[i] + 1
        else:
            s[i + 1] = s[i] - 1
    if count_inversion(s) * 2 >= m:
        if ans == l:
            break
        elif ans == l + 1:
            ans = l
            break
        else:
            r = ans
            ans = l + (ans - l) // 2
    else:
        if ans == r:
            break
        else:
            l = ans
            ans = ans + (r - ans) // 2 + 1

print(b[ans])

Submission status: Wrong Answer

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

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

    def bit_add(i):
        x = i
        while x < 2 * n + 8:
            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

    res = 0
    for i in range(len(input_array)):
        x = input_array[i] + n + 4
        res += i - bit_sum(x)
        bit_add(x)
    return res

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

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

ans = len(b) // 2

l = 0
r = len(b) - 1
while 1:
    s = [n for _ in range(n + 1)]
    s[0] = n + 1
    for i in range(n):
        if a[i] >= b[ans]:
            s[i] = s[i - 1] + 1
        else:
            s[i] = s[i - 1] - 1
    if count_inversion(s) * 2 >= m:
        if ans == l:
            break
        elif ans == l + 1:
            ans = l
            break
        else:
            r = ans
            ans = l + (ans - l) // 2
    else:
        if ans == r:
            break
        else:
            l = ans
            ans = ans + (r - ans) // 2 + 1

print(b[ans])

Submission status: Wrong Answer

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

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

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

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

    res = 0
    for i in range(len(input_array)):
        x = input_array[i] + n + 5
        res += i - bit_sum(x)
        bit_add(x)
    return res

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

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

ans = len(b) // 2

l = 0
r = len(b) - 1
while 1:
    s = [n for _ in range(n + 1)]
    s[0] = n + 1
    for i in range(n):
        if a[i] >= b[ans]:
            s[i] = s[i - 1] + 1
        else:
            s[i] = s[i - 1] - 1
    if count_inversion(s) * 2 >= m:
        if ans == l:
            break
        elif ans == l + 1:
            ans = l
            break
        else:
            r = ans
            ans = l + (ans - l) // 2
    else:
        if ans == r:
            break
        else:
            l = ans
            ans = ans + (r - ans) // 2 + 1

print(b[ans])

Submission status: Wrong Answer

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

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

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

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

    res = 0
    for i in range(len(input_array)):
        x = input_array[i]
        res += i - bit_sum(x)
        bit_add(x)
    return res

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

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

ans = len(b) // 2

l = 0
r = len(b) - 1
while 1:
    s = [n for _ in range(n)]
    s[0] = n
    for i in range(1,n):
        if a[i] >= b[ans]:
            s[i] = s[i - 1] + 1
        else:
            s[i] = s[i - 1] - 1
    base = min(s)
    for i in range(n):
        s[i] -= base - 1
    if count_inversion(s) * 2 >= m:
        if ans == l:
            break
        elif ans == l + 1:
            ans = l
            break
        else:
            r = ans
            ans = l + (ans - l) // 2
    else:
        if ans == r:
            break
        else:
            l = ans
            ans = ans + (r - ans) // 2 + 1

print(b[ans])

Submission status: Wrong Answer

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


class BIT:
    # index 1~
    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


M = N * (N + 1) // 2  # (N+1)C2
sorted_A = sorted(A)

print(M)
inf = 0
sup = max(A) + 1
while sup - inf > 1:
    x = (sup + inf) // 2
    print(inf, sup, x)

    S = [0] * (N + 1)
    for i in range(N):
        if A[i] >= x:
            S[i + 1] = S[i] + 1
        else:
            S[i + 1] = S[i] - 1

    print([1 if a >= x else -1 for a in A])

    min_value = min(S)
    for i in range(N + 1):
        S[i] += abs(min_value) + 1

    print(S)
    forward = 0
    bit = BIT(max(S))
    for s in S:
        forward += bit.sum(s)
        bit.add(s, 1)
        print(s, bit.tree, bit.sum(s), forward)

    if forward >= (M + 1) // 2:
        inf = x
    else:
        sup = x

for a in reversed(sorted_A):
    if inf >= a:
        print(a)
        break

Submission status: Wrong Answer

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

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

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

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

    res = 0
    for i in range(len(input_array)):
        x = input_array[i]
        res += i - bit_sum(x)
        bit_add(x)
    return res

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

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

ans = len(b) // 2

l = 0
r = len(b) - 1
#print(b, m)
while 1:
    s = [n for _ in range(n)]
    s[0] = n
    for i in range(1,n):
        if a[i] >= b[ans]:
            s[i] = s[i - 1] + 1
        else:
            s[i] = s[i - 1] - 1
    base = min(s)
    for i in range(n):
        s[i] -= base - 1
    #print(s, count_inversion(s), l, r, ans)
    if count_inversion(s) * 2 >= m:
        if ans == l:
            break
        elif ans == l + 1:
            ans = l
            break
        else:
            r = ans
            ans = l + (ans - l) // 2
    else:
        if ans == r:
            break
        else:
            l = ans
            ans = ans + (r - ans) // 2 + 1

print(b[ans])

Submission status: Wrong Answer

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

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

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

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

    res = 0
    for i in range(len(input_array)):
        x = input_array[i]
        res += i - bit_sum(x)
        bit_add(x)
    return res

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

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

ans = len(b) // 2

l = 0
r = len(b) - 1
#print(b, m)
while 1:
    s = [n for _ in range(n)]
    s[0] = n
    for i in range(1,n):
        if a[i] >= b[ans]:
            s[i] = s[i - 1] + 1
        else:
            s[i] = s[i - 1] - 1
    base = min(s)
    for i in range(n):
        s[i] -= base - 1
    #print(s, count_inversion(s), l, r, ans)
    if count_inversion(s) > m:
        if ans == l:
            break
        elif ans == l + 1:
            ans = l
            break
        else:
            r = ans
            ans = l + (ans - l) // 2
    else:
        if ans == r:
            break
        else:
            l = ans
            ans = ans + (r - ans) // 2 + 1

print(b[ans])

Submission status: Wrong Answer

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: Wrong Answer

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: Wrong Answer

Solution code:
N=int(input())
a=[int(i) for i in input().split()]
A=len(bin(N))-2
B=len(bin(max(a)))-2
ans=0
for i in range(N):
    for j in range(A):
        for k in range(B):
            ans+=1
print(3)

Submission status: Wrong Answer

Solution code:
n = int(input())
array = sorted(list(map(int,input().split(" "))))
array2 = []
for r in range(n):
    for l in range(r,n):
        m_rl = array[r:l+1]
        array2.append(m_rl[(l-r)//2])
array2 = sorted(array2)
med = (int((n+1)*n/2))//2
print(array2[med])

Submission status: Wrong Answer

Solution code:
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(mid):
    x = b[mid]

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

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


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

print(b[right])

Submission status: Wrong Answer

Solution code:
# 参考: https://beta.atcoder.jp/contests/arc101/submissions/3082640
import math

N = int(input())
a = [int(x) for x in input().split()]

b = sorted(a)


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


M = math.ceil(N * (N + 1) // 2 / 2)
left, right = 0, N - 1
while right - left > 1:
    mid = (left + right) // 2
    x = b[mid]

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

    bit = BIT(max_S - min_S + 1)
    cnt = 0
    for i in range(N):
        S_i = S[i] - min_S + 1
        cnt += bit.sum(S_i)
        bit.add(S_i, 1)

    if cnt >= M:
        left = mid
    else:
        right = mid

print(b[right])

Submission status: Wrong Answer

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: Wrong Answer

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)
    m = a_sort[(left + right + 1) // 2]
    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 - 1 - i)
    # update left of right
    if sum_a < 0: right = (left + right + 1) // 2 - 1
    else: left = (left + right + 1) // 2
    # escape
    if left == right: break

# ans
# t2 = time.time()
# print("#", t2 - t1)
print(a_sort[left])

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
a = [int(x) for x in input().split()]

b = sorted(a)


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


M = math.ceil(N * (N + 1) // 2 / 2)
left, right = 0, N - 1
while right - left > 1:
    # print('l: b[{}]={}, r: b[{}]={}'.format(left, b[left], right, b[right]))
    mid = (left + right) // 2
    x = b[mid]

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

    bit = BIT(max_S - min_S + 1)
    cnt = 0
    for i in range(N):
        S_i = S[i] - min_S + 1
        cnt += bit.sum(S_i)
        bit.add(S_i, 1)
    # print('mid: b[{}]={}, {} >= {}, {}'.format(mid, b[mid], cnt, M, cnt >= M))

    if cnt >= M:
        left = mid
    else:
        right = mid

print(b[left])

Submission status: Wrong Answer

Solution code:
#encoding utf 8
n = int(input())

a = list(int(i) for i in input().split())

def midle_pos(midle):
    return int(midle/2)

m = a
for i in range(1,n+1):
    b = []
    for j in range(i):
        b.append(a[j])
    b.sort()
    m.append(b[midle_pos(i)])

m.sort()
# print(m)
len = len(m)
print(m[midle_pos(len)])

Submission status: Wrong Answer

Solution code:
N = int(input().strip())
count = [1 for i in range(N)]

if N % 2 == 0:
    for i in range(N//2):
        count[N-i-1] = N - (N - i) + 1
        count[i] = N - (N - i) + 2
else:
    if N > 1:
        for i in range(N//2):
            count[N-i-1] = N - (N - i) + 1
            count[i] = N - (N - i) + 2
        count[N//2 + 1] = N
    else:
        count[0] = 1

index = 0
base = [int(i) for i in input().strip().split(" ")]
ans = []
for i in base:
    for j in range(count[index]):
        ans.append(i)
    index += 1
if N == 1:
    print(ans[0])
else:
    print(ans)
    print(sorted(ans)[len(ans)//2+1])

Submission status: Wrong Answer

Solution code:
N = int(input())
a = [int(i) for i in input().split()]
a.sort()
if N == 1:
    print(a[0])
elif N==2:
    print(a[1])
elif N==3:
    print(a[2])
elif N<11:
    print(a[N//2+1])
else:
    print(a[N//2+2])

Submission status: Wrong Answer

Solution code:
_ = input()
a = 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: Wrong Answer

Solution code:
def find_median(input_list):
    length = len(input_list)
    if length%2:
        return input_list[length//2]
    else:
        return input_list[int(length/2)]

import statistics

N = input()
a = list(map(int,input().split()))
ans_list = []
for i in range(len(a)):
    for idx in range(len(a)-i):
        ans_list.append(find_median(a[idx:(idx+i+1)]))

print(find_median(ans_list))

Submission status: Wrong Answer

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

if N % 2 == 1:
    print(a[N // 2])
else:
    print(min(a[N // 2], a[N // 2 - 1]))

Submission status: Wrong Answer

Solution code:
from math import ceil
n=int(input())
a=sorted([int(i) for i in input().split()])
x=2
y=0
for i in range(n):
  if n>=x**2:
    x=x**2
    y+=1

if n==1:
  print(a[0])
elif n % 2 == 1:
  print(a[ceil(n/2)])
else:
  print(a[ceil(n/2)+y-2])

Submission status: Wrong Answer

Solution code:
n = int(raw_input())
lis = map(int, raw_input().split())
lis = sorted(lis)
val = ((n*(n+1))/2)
idx = (val/2)+1
summ=0
z=1
#print idx
#print lis
flag=0
for i in xrange(n):
    summ+=(z)
    z+=1
    #print summ
    if summ>=idx:
        #print idx
        print lis[i]
        flag=1
        break
if flag==0:
    print lis[n-1]

Submission status: Wrong Answer

Solution code:
N = int(input())
a = [int(i) for i in input().split()]
a.sort()
if N == 1:
    print(a[0])
elif N==2:
    print(a[1])
elif N==3:
    print(a[2])
else:
    print(a[N//2+1])

Submission status: Wrong Answer

Solution code:
# encoding: utf-8
N = int(input())
a = list(map(int, input().split()))

dict_count = {}
seq_list = []
# count num of submeds
for i, ai in enumerate(a):
    # existing sequences
    for seq in seq_list:
        seq_temp = list(seq)
        for k in range(len(seq)):
            if ai <= seq[k]:
                seq_temp.insert(k, ai)
                break
        else:
            seq_temp.insert(-1, ai)
        # update dict
        submed = seq_temp[len(seq_temp) // 2]
        if submed in dict_count.keys(): dict_count[str(submed)] += 1
        else: dict_count[str(submed)] = 1
    # new sequence [ai]
    seq_list.append([ai])
    if ai in dict_count.keys(): dict_count[str(ai)] += 1
    else: dict_count[str(ai)] = 1

# ans
keys = sorted(dict_count.keys())
med = sum(dict_count.values()) // 2
med_temp = 0
for key in keys:
    med_temp += dict_count[key]
    if med_temp >= med:
        print(key)
        break

Submission status: Wrong Answer

Solution code:
import statistics

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

l = []

if n > 300:
    a = a[n//2-150:n//2+150]

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))