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:
class BIT:
    '''
    0-indexed
    '''
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.depth = n.bit_length()

    def _bitsum(self, i):
        ret = 0
        while i:
            ret += self.tree[i]
            i ^= i & -i
        return ret

    def bitsum(self, l, r=None): # [l, r)
        if r is None:
            return self._bitsum(l)
        else:
            return self._bitsum(r) - self._bitsum(l)

    def bitadd(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        return

n = int(input())
m = (n * (n - 1) // 2) // 2
a = list(map(int, input().split()))
d = dict()
_a = sorted(set(a))
for i, x in enumerate(_a):
  d[x] = i
a = [d[x] for x in a]


def check(X):
  b = [0] + [(y>=X)*2 - 1 for y in a]
  for i in range(n):
    b[i+1] += b[i]
  c = min(b)
  b = [x-c for x in b] 
  bit = BIT(n + 10)
  ans = 0
  for x in b:
    ans += bit.bitsum(x+1)
    bit.bitadd(x, 1)
  return ans >= m

t = [len(_a), -1]
while t[0] - t[1] > 1:
  mid = (t[0] + t[1]) // 2
  t[check(mid)] = mid
print(_a[t[1]])

Submission status: Wrong Answer

Solution code:
class BIT:
    '''
    0-indexed
    '''
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.depth = n.bit_length()

    def _bitsum(self, i):
        ret = 0
        while i:
            ret += self.tree[i]
            i ^= i & -i
        return ret

    def bitsum(self, l, r=None): # [l, r)
        if r is None:
            return self._bitsum(l)
        else:
            return self._bitsum(r) - self._bitsum(l)

    def bitadd(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        return

n = int(input())
m = (n * (n - 1) // 2) // 2 + 1
a = list(map(int, input().split()))
d = dict()
_a = sorted(set(a))
for i, x in enumerate(_a):
  d[x] = i
a = [d[x] for x in a]


def check(X):
  b = [0] + [(y>=X)*2 - 1 for y in a]
  for i in range(n):
    b[i+1] += b[i]
  c = min(b)
  b = [x-c for x in b] 
  bit = BIT(max(b) + 10)
  ans = 0
  for x in b:
    ans += bit.bitsum(x+1)
    bit.bitadd(x, 1)
  return ans >= m

t = [len(_a) + 1, -1]
while t[0] - t[1] > 1:
  mid = (t[0] + t[1]) // 2
  t[check(mid)] = mid
print(_a[t[1]])

Submission status: Wrong Answer

Solution code:
class BIT:
    '''
    0-indexed
    '''
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.depth = n.bit_length()

    def _bitsum(self, i):
        ret = 0
        while i:
            ret += self.tree[i]
            i ^= i & -i
        return ret

    def bitsum(self, l, r=None): # [l, r)
        if r is None:
            return self._bitsum(l)
        else:
            return self._bitsum(r) - self._bitsum(l)

    def bitadd(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        return

n = int(input())
m = (n * (n - 1) // 2) // 2 + 1
a = list(map(int, input().split()))
d = dict()
_a = sorted(set(a))
for i, x in enumerate(_a):
  d[x] = i
a = [d[x] for x in a]


def check(X):
  b = [0] + [(y>=X)*2 - 1 for y in a]
  for i in range(n):
    b[i+1] += b[i]
  c = min(b)
  b = [x-c for x in b] 
  bit = BIT(n + 10)
  ans = 0
  for x in b:
    ans += bit.bitsum(x+1)
    bit.bitadd(x, 1)
  return ans >= m

t = [len(_a) + 1, -1]
while t[0] - t[1] > 1:
  mid = (t[0] + t[1]) // 2
  t[check(mid)] = mid
print(_a[t[1]])

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a2=sorted(set(a))
L=len(a2)
if n==1:print(a[0]);exit()
elif n==2:print(a[1]);exit()
ng=L
ok=0
while ng-ok>1:
    check=a2[(ok+ng)//2]
    cnt=0 #check以上の要素の数
    idx=n
    cl=[0]*(2*n+1)
    Ru=0
    for i in range(n):
        if a[i]<check:
            Ru-=cl[idx]-1
            idx-=1
        else:
            Ru+=cl[idx]
            idx+=1
        cnt += Ru
        cl[idx]+=1
    if cnt >= ((n+1)*n)//4:
        ok = (ok+ng)//2
    else:
        ng = (ok+ng)//2
print(a2[ok])

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
from collections import defaultdict
class Bit:
  def __init__(self,n):
    self.size = n
    self.tree = [0]*(n+1)
 
  def sum(self,i):
    s = 0
    while i > 0:
      s += self.tree[i]
      i -= i & -i
    return s

  def add(self,i,x):
    while i <= self.size:
      self.tree[i] += x
      i += i & -i
n = int(input())
a = list(map(int,input().split()))
def jdg(x):
  b = [0 for i in range(n)]
  for i in range(n):
    if a[i] >= x:
      b[i] = 1
    else:
      b[i] = -1
  acc = [0]+list(accumulate(b))
  mn = min(acc)
  mx = max(acc)
  dif = mx-mn
  bit = Bit(dif+2)
  ret = 0
  for i in range(n+1):
    p = acc[i]-mn+1
    ret += bit.sum(p)
    bit.add(p,1)
  return ret
l = 0
r = max(a)+1
while l+1 < r:
  x = (l+r)//2
  if jdg(x) >= (n+1)*n//4+1:
    l = x
  else:
    r = x
print(l)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
from collections import defaultdict
class Bit:
  def __init__(self,n):
    self.size = n
    self.tree = [0]*(n+1)
 
  def sum(self,i):
    s = 0
    while i > 0:
      s += self.tree[i]
      i -= i & -i
    return s

  def add(self,i,x):
    while i <= self.size:
      self.tree[i] += x
      i += i & -i
n = int(input())
a = list(map(int,input().split()))
def jdg(x):
  b = [0 for i in range(n)]
  for i in range(n):
    if a[i] >= x:
      b[i] = 1
    else:
      b[i] = -1
  acc = list(accumulate(b))
  mn = min(acc)
  mx = max(acc)
  dif = mx-mn
  bit = Bit(dif+2)
  ret = 0
  for i in range(n):
    p = acc[i]-mn+1
    ret += bit.sum(p)
    bit.add(p,1)
  return ret
l = 0
r = max(a)+1
while l+1<r:
  x = (l+r)//2
  if jdg(x) > (n-1)*n//4+1:
    l = x
  else:
    r = x-1
print(r)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
print(A[(N+1)//2-1])

Submission status: Wrong Answer

Solution code:
def examA():
    N, i = LI()
    ans = N - i + 1
    print(ans)
    return

def examB():
    H, W = LI()
    A = [SI() for _ in range(H)]
    h = [[]for _ in range(H)]
    for i in range(W):
        flag = False
        for j in range(H):
            if A[j][i]=="#":
                flag = True
                break
        if flag:
            for j in range(H):
                h[j].append(A[j][i])
    #print(h)
    ans = []
    for i,a in enumerate(h):
        if "#" in a:
            ans.append(i)
    for v in ans:
        print("".join(map(str,h[v])))
    return

def examC():
    N, K = LI()
    X = LI()
    ans = inf
    for i in range(N-K+1):
        if X[i]<0 and X[i+K-1]>0:
            cur = (-X[i] + X[i+K-1]) + min(-X[i], X[i+K-1])
        else:
            cur = max(-X[i], X[i+K-1])
        ans = min(ans,cur)
    print(ans)
    return

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

        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
            return
    def inversion_number(n,A):
        bit = Bit(n+1)
        rep = 0
        for i, a in enumerate(A):
            bit.add(a, 1)
            rep += i + 1 - bit.sum(a)
        return rep
    N = I()
    A = LI()
    judge = (N*(N+1)//2 + 1)//2
    l = 0; r = max(A)+1
    while(r-l>1):
        #print(l,r)
        now = (l+r)//2
        S = [0]*N
        cur = N*(N+1)//2
        for i in range(N):
            if A[i]>=now:
                S[i] += 1
            else:
                S[i] -= 1
                cur -= 1
        for i in range(N-1):
            S[i+1] += S[i]
            S[i] += N
        S[-1] += N
        #print(S)
        cur -= inversion_number(2*N+10,S)
        #print(cur,now)
        #input()
        if cur>=judge:
            l = now
        else:
            r = now

    ans = l
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

"""

"""

Submission status: Wrong Answer

Solution code:
def examA():
    N, i = LI()
    ans = N - i + 1
    print(ans)
    return

def examB():
    H, W = LI()
    A = [SI() for _ in range(H)]
    h = [[]for _ in range(H)]
    for i in range(W):
        flag = False
        for j in range(H):
            if A[j][i]=="#":
                flag = True
                break
        if flag:
            for j in range(H):
                h[j].append(A[j][i])
    #print(h)
    ans = []
    for i,a in enumerate(h):
        if "#" in a:
            ans.append(i)
    for v in ans:
        print("".join(map(str,h[v])))
    return

def examC():
    N, K = LI()
    X = LI()
    ans = inf
    for i in range(N-K+1):
        if X[i]<0 and X[i+K-1]>0:
            cur = (-X[i] + X[i+K-1]) + min(-X[i], X[i+K-1])
        else:
            cur = max(-X[i], X[i+K-1])
        ans = min(ans,cur)
    print(ans)
    return

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

        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
            return
    def inversion_number(n,A):
        bit = Bit(n+1)
        rep = 0
        for i, a in enumerate(A):
            bit.add(a, 1)
            rep += i + 1 - bit.sum(a)
        return rep
    N = I()
    A = LI()
    l = 0; r = max(A)+1
    while(r-l>1):
        #print(l,r)
        now = (l+r)//2
        S = [0]*N
        cur = N*(N+1)//2
        for i in range(N):
            if A[i]>=now:
                S[i] += 1
            else:
                S[i] -= 1
                cur -= 1
        for i in range(N-1):
            S[i+1] += S[i]
            S[i] += N
        S[-1] += N
        #print(S)
        cur -= inversion_number(2*N+10,S)
        #print(cur,now)
        #input()
        if cur>=(N*(N+1)//2)//2:
            l = now
        else:
            r = now

    ans = l
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

"""

"""

Submission status: Wrong Answer

Solution code:
def examA():
    N, i = LI()
    ans = N - i + 1
    print(ans)
    return

def examB():
    H, W = LI()
    A = [SI() for _ in range(H)]
    h = [[]for _ in range(H)]
    for i in range(W):
        flag = False
        for j in range(H):
            if A[j][i]=="#":
                flag = True
                break
        if flag:
            for j in range(H):
                h[j].append(A[j][i])
    #print(h)
    ans = []
    for i,a in enumerate(h):
        if "#" in a:
            ans.append(i)
    for v in ans:
        print("".join(map(str,h[v])))
    return

def examC():
    N, K = LI()
    X = LI()
    ans = inf
    for i in range(N-K+1):
        if X[i]<0 and X[i+K-1]>0:
            cur = (-X[i] + X[i+K-1]) + min(-X[i], X[i+K-1])
        else:
            cur = max(-X[i], X[i+K-1])
        ans = min(ans,cur)
    print(ans)
    return

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

        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
            return
    def inversion_number(n,A):
        bit = Bit(n+1)
        rep = 0
        for i, a in enumerate(A):
            bit.add(a, 1)
            rep += i + 1 - bit.sum(a)
        return rep
    N = I()
    A = LI()
    l = 0; r = max(A)+1
    while(r-l>1):
        #print(l,r)
        now = (l+r)//2
        S = [0]*N
        cur = N*(N+1)//2
        for i in range(N):
            if A[i]>=now:
                S[i] += 1
            else:
                S[i] -= 1
                cur -= 1
        for i in range(N-1):
            S[i+1] += S[i]
            S[i] += N
        S[-1] += N
        #print(S)
        cur -= inversion_number(2*N+1,S)
        #print(cur,now)
        #input()
        if cur>=(N*(N+1)//2)//2:
            l = now
        else:
            r = now

    ans = l
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

"""

"""

Submission status: Wrong Answer

Solution code:
def examA():
    N, i = LI()
    ans = N - i + 1
    print(ans)
    return

def examB():
    H, W = LI()
    A = [SI() for _ in range(H)]
    h = [[]for _ in range(H)]
    for i in range(W):
        flag = False
        for j in range(H):
            if A[j][i]=="#":
                flag = True
                break
        if flag:
            for j in range(H):
                h[j].append(A[j][i])
    #print(h)
    ans = []
    for i,a in enumerate(h):
        if "#" in a:
            ans.append(i)
    for v in ans:
        print("".join(map(str,h[v])))
    return

def examC():
    N, K = LI()
    X = LI()
    ans = inf
    for i in range(N-K+1):
        if X[i]<0 and X[i+K-1]>0:
            cur = (-X[i] + X[i+K-1]) + min(-X[i], X[i+K-1])
        else:
            cur = max(-X[i], X[i+K-1])
        ans = min(ans,cur)
    print(ans)
    return

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

        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
            return
    def inversion_number(n,A):
        bit = Bit(n+1)
        rep = 0
        for i, a in enumerate(A):
            bit.add(a, 1)
            rep += i + 1 - bit.sum(a)
        return rep
    N = I()
    A = LI()
    l = 0; r = max(A)+1
    while(r-l>1):
        #print(l,r)
        now = (l+r)//2
        S = [0]*N
        cur = N*(N+1)//2
        for i in range(N):
            if A[i]>=now:
                S[i] += 1
            else:
                S[i] -= 1
                cur -= 1
        for i in range(N-1):
            S[i+1] += S[i]
            S[i] += N
        S[-1] += N
        #print(S)
        cur -= inversion_number(2*N,S)
        #print(cur,now)
        #input()
        if cur>=(N*(N+1)//2)//2:
            l = now
        else:
            r = now

    ans = l
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

"""

"""

Submission status: Wrong Answer

Solution code:
def examA():
    N, i = LI()
    ans = N - i + 1
    print(ans)
    return

def examB():
    H, W = LI()
    A = [SI() for _ in range(H)]
    h = [[]for _ in range(H)]
    for i in range(W):
        flag = False
        for j in range(H):
            if A[j][i]=="#":
                flag = True
                break
        if flag:
            for j in range(H):
                h[j].append(A[j][i])
    #print(h)
    ans = []
    for i,a in enumerate(h):
        if "#" in a:
            ans.append(i)
    for v in ans:
        print("".join(map(str,h[v])))
    return

def examC():
    N, K = LI()
    X = LI()
    ans = inf
    for i in range(N-K+1):
        if X[i]<0 and X[i+K-1]>0:
            cur = (-X[i] + X[i+K-1]) + min(-X[i], X[i+K-1])
        else:
            cur = max(-X[i], X[i+K-1])
        ans = min(ans,cur)
    print(ans)
    return

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

        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
            return
    def inversion_number(n,A):
        bit = Bit(n+1)
        rep = 0
        for i, a in enumerate(A):
            bit.add(a, 1)
            rep += i + 1 - bit.sum(a)
        return rep
    N = I()
    A = LI()
    l = 0; r = max(A)+1
    while(r-l>1):
        #print(l,r)
        now = (l+r)//2
        S = [0]*N
        cur = N*(N+1)//2
        for i in range(N):
            if A[i]>=now:
                S[i] += 1
            else:
                S[i] -= 1
                cur -= 1
        for i in range(N-1):
            S[i+1] += S[i]
            S[i] += N
        S[-1] += N
        #print(S)
        cur -= inversion_number(2*N,S)
        #print(cur,now)
        #input()
        if cur>=(N*(N+1)//2 + 1)//2:
            l = now
        else:
            r = now

    ans = l
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

"""

"""

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
sortA=a+[float('inf')]
def isOK(m):
  x=sortA[m]
  cnt=[0]*(2*n+1)
  cnt[n+1]=1
  i=n+1
  s=1
  res=0
  for b in a:
    if b>=x:
      i+=1
      s+=cnt[i]
    else:
      s-=cnt[i]
      i-=1
    res+=s
    cnt[i]+=1
    s+=1
    if res>=n*(n+1)//4:
      return False
    else:
      return True
l,r=0,len(sortA)-1
while r-l>1:
  mid=(r+l)//2
  if isOK(mid):
    r=mid
  else:
    l=mid
print(sortA[l])

Submission status: Wrong Answer

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

def median(l, r, a):
    if l == r:
        return a[r]
    else:
        c = a[l:r+1]
        c = sorted(c)
        return c[int(len(c)/2)]

for l in range(n):
    for r in range(n):
        if l <= r:
            b.append(median(l, r, a))
        

print(b[int(len(b)/2)])

Submission status: Wrong Answer

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

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

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


n = int(input())
A = list(map(int, input().split()))
all_pattern = n * (n+1) // 2
check = all_pattern // 2 + bool(all_pattern % 2)
X = sorted(A)

left = 0
right = n

while left + 1 < right:
    idx = (left+right) // 2
    x = X[idx]
    up_or_down = [1 if num >= x else -1 for num in A]
    cumsum = []
    total = 0
    for point in up_or_down:
        total += point
        cumsum.append(total+n)

    tree = Bit(2*n+1)
    pattern = 0
    for p in cumsum:
        tree.add(p, 1)
        pattern += tree.sum(p)

    if pattern >= check:
        left = idx
    else:
        right = idx

print(X[left])

Submission status: Wrong Answer

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

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

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


n = int(input())
A = list(map(int, input().split()))
all_pattern = n * (n+1) // 2
check = all_pattern // 2
X = sorted(A)

left = 0
right = n

while left + 1 < right:
    idx = (left+right) // 2
    x = X[idx]
    up_or_down = [1 if num >= x else -1 for num in A]
    cumsum = []
    total = 0
    for point in up_or_down:
        total += point
        cumsum.append(total+n)

    tree = Bit(2*n+1)
    pattern = 0
    for p in cumsum:
        tree.add(p, 1)
        pattern += tree.sum(p)

    if pattern >= check:
        left = idx
    else:
        right = idx

print(X[left])

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
NN = ((N + 1) * N // 2 + 1) // 2

def ok(x):
    B = [0] * (2 * N + 1)
    res, cum, cur = 0, 0, 0
    for a in A:
        B[cum] += 1
        if a >= x:
            cur += B[cum]+1
            cum += 1
        else:
            cum -= 1
            cur -= B[cum]
        res += cur
    return res >= NN

B = sorted(set(A))
l = 0
r = len(B)
while r - l > 1:
    m = (l + r) // 2
    if ok(B[m]):
        l = m
    else:
        r = m
print(B[l])

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
import numpy as np
N = int(input())
A = list(map(int, input().split()))
NN = ((N + 1) * N // 2 + 1) // 2
def ok(x):
    S = np.fromiter((1 if a >= x else -1 for a in [0]+A), dtype=np.int32)
    S += - min(S.min(), 0) + 1
    S[0] = 1
    L = max(S) + 1
    B = np.zeros(L, dtype=np.int32)
    c = 0
    for s in S:
        i = s
        while i > 0:
            c += B[i]
            i -= i & -i
        i = s
        while i < L:
            B[i] += 1
            i += i & -i
    return c >= NN

B = sorted(set(A))
l = 0
r = len(B)
while r - l > 1:
    m = (l + r) // 2
    if ok(B[m]):
        l = m
    else:
        r = m
print(B[l])

Submission status: Wrong Answer

Solution code:
class BIT:
    def __init__(self, n):
        self.N = n
        self.n = 1<<n.bit_length()
        self.data = [0] * (self.n + 1)
        
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.n:
            self.data[i] += x
            i += i & -i
N = int(input())
A = list(map(int, input().split()))
N0 = N*(N+1)//2
def C(x):
    B = BIT(N*2+1)
    s = [0]*(N+1)
    for i in range(N):
        a = A[i]
        s[i] = 1 if x<a else -1
        s[i]+=s[i-1]
    res = 0
    for i in range(-1, N):
        res+=B.sum(s[i]+N+1)
        B.add(s[i]+N+1, 1)
    return res<=N0//2
ok = max(A)
ng = min(A)-1
while abs(ok-ng)>1:
    mid = (ok+ng)//2
    if C(mid):#midが条件を満たすか
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Wrong Answer

Solution code:
import sys

def bit_add(iii,x):
    while iii<len(bit):
        bit[iii]+=x
        iii+=iii&(-iii)
def bit_sum(jjj):
    s=0
    while jjj>0:
        s+=bit[jjj]
        jjj-=jjj&(-jjj)
    return s

n=int(input())
a=list(map(int,input().split()))
num=n*(n+1)//2

high=max(a)
low=min(a)

while high-low>1:
    mid=(high+low)//2
    
    ans=0
    b=[]
    for i in range(n):
        if a[i]>=mid:
            b.append(1)
        else:
            b.append(-1)

    for i in range(1,n):
        b[i]+=b[i-1]
    for i in range(n):
        b[i]+=n
    
    bit=[0]*(2*n+3)
    bit_add(n,1)

    for i in range(n):
        ans+=bit_sum(b[i])
        bit_add(b[i],1)

    if num%2==1:
        if ans>=num//2+1:
            low=mid
        else:
            high=mid
    else:
        if ans>=num//2:
            low=mid
        else:
            high=mid

if not high in a:
    print(low)
    sys.exit()
            
mid=high
ans=0
    
b=[]
for i in range(n):
    if a[i]>=mid:
        b.append(1)
        ans+=1
    else:
        b.append(-1)
for i in range(1,n):
    b[i]+=b[i-1]
for i in range(n):
    b[i]+=n

bit=[0]*(2*n+3)
bit_add(n,1)

for i in range(n):
    ans+=bit_sum(b[i])
    bit_add(b[i],1)

if num%2==1:
    if ans>=num//2+1:
        print(high)
    else:
        print(low)
else:
    if ans>=num//2:
        print(high)
    else:
        print(low)

Submission status: Wrong Answer

Solution code:
import sys

def bit_add(iii,x):
    while iii<len(bit):
        bit[iii]+=x
        iii+=iii&(-iii)
def bit_sum(jjj):
    s=0
    while jjj>0:
        s+=bit[jjj]
        jjj-=jjj&(-jjj)
    return s

n=int(input())
a=list(map(int,input().split()))
num=n*(n+1)//2

high=max(a)
low=min(a)

while high-low>1:
    mid=(high+low)//2
    ans=0
    b=[]
    for i in range(n):
        if a[i]>=mid:
            b.append(1)
            ans+=1
        else:
            b.append(-1)
    for i in range(1,n):
        b[i]+=b[i-1]
        if b[i]>=0:
            ans+=1
    for i in range(n):
        b[i]+=n
    
    bit=[0]*(2*n+3)
    for i in range(n):
        ans+=bit_sum(b[i])
        bit_add(b[i],1)

    if num%2==1:
        if ans>=num//2+1:
            low=mid
        else:
            high=mid
    else:
        if ans>=num//2:
            low=mid
        else:
            high=mid

if not high in a:
    print(low)
    sys.exit()
            
mid=high
ans=0
    
b=[]
for i in range(n):
    if a[i]>=mid:
        b.append(1)
        ans+=1
    else:
        b.append(-1)
for i in range(1,n):
    b[i]+=b[i-1]
    if b[i]>=0:
        ans+=1
for i in range(n):
    b[i]+=n

bit=[0]*(2*n+3)
for i in range(n):
    ans+=bit_sum(b[i])
    bit_add(b[i],1)

if num%2==1:
    if ans>=num//2+1:
        print(high)
    else:
        print(low)
else:
    if ans>=num//2:
        print(high)
    else:
        print(low)

Submission status: Wrong Answer

Solution code:
def bit_add(iii,x):
    while iii<len(bit):
        bit[iii]+=x
        iii+=iii&(-iii)
def bit_sum(jjj):
    s=0
    while jjj>0:
        s+=bit[jjj]
        jjj-=jjj&(-jjj)
    return s

n=int(input())
a=list(map(int,input().split()))
num=n*(n+1)//2

high=max(a)
low=min(a)

while high-low>1:
    mid=(high+low)//2
    ans=0
    
    b=[]
    for i in range(n):
        if a[i]>=mid:
            b.append(1)
            ans+=1
        else:
            b.append(-1)
    for i in range(1,n):
        b[i]+=b[i-1]
    for i in range(n):
        b[i]+=n
    
    bit=[0]*(2*n+3)
    for i in range(n):
        ans+=bit_sum(b[i])
        bit_add(b[i],1)

    if num%2==1:
        if ans>=num//2+1:
            low=mid
        else:
            high=mid
    else:
        if ans>=num//2:
            low=mid
        else:
            high=mid


mid=high
ans=0
    
b=[]
for i in range(n):
    if a[i]>=mid:
        b.append(1)
        ans+=1
    else:
        b.append(-1)
for i in range(1,n):
    b[i]+=b[i-1]
for i in range(n):
    b[i]+=n

bit=[0]*(2*n+3)
for i in range(n):
    ans+=bit_sum(b[i])
    bit_add(b[i],1)

if num%2==1:
    if ans>=num//2+1:
        print(high)
    else:
        print(low)
else:
    if ans>=num//2:
        print(high)
    else:
        print(low)