Harryxun/stf_run huggingface dataset:
from itertools import groupby
from heapq import heapify, heappop

N, K = map(int, input().split())
sushi = [tuple(map(int, input().split())) for _ in range(N)]

srt = sorted(sushi, key=lambda x: x[1], reverse=True)
eat, non_eat = srt[:K], srt[K:]

maxs = []
rems = []
kinds = set()
for k, g in groupby(sorted(eat, key=lambda x: x[0]), key=lambda x: x[0]):
    d = list(list(zip(*g))[1])
    maxs.append(d.pop(0))
    rems.extend(d)
    kinds.add(k)
heapify(rems)
ans = sum(maxs) + sum(rems) + len(kinds)**2

for k, g in groupby(sorted(non_eat, key=lambda x: x[0]), key=lambda x: x[0]):
    if k in kinds:
        continue
    if not rems:
        break
    d = list(list(zip(*g))[1])
    maxs.append(d.pop(0))
    heappop(rems)
    kinds.add(k)
    ans = max(ans, sum(maxs) + sum(rems) + len(kinds)**2)

print(ans)


### FIXED CODE ###

a,b,c = map(int, input().split())

print(a*b//2)
K, N = map(int, input().split())
A = list(map(int(input().split())))

K.append(A[0]+K)
l = K+1
for i in range(N):
  l = min(l, A[i+1]-A[i])

print(K-l)

### FIXED CODE ###

K, N = map(int, input().split())
A = list(map(int, input().split()))
 
A.append(A[0]+K)
l = 0
for i in range(N):
  l = max(l, A[i+1]-A[i])

print(K-l)
c = input()
s = "abcdefghijklmnopqrstuvwxyz"
flg = True
for i in range(len(s) + 1):
    if c == s[i] and c != "z":
        print(s[i + 1])
        flg = False
    elif c == "z":
        print("a")
        flg = False


### FIXED CODE ###

c = input()
s = "abcdefghijklmnopqrstuvwxyz"
flg = True
for i in range(len(s) + 1):
    if c == s[i] and c != "z":
        print(s[i + 1])
        break
    elif c == "z":
        print("a")
        break
N,K = map(int,input().split())
D = set(map(int,input().split()))
ans = N
while(True):
  if any(i in D for i in list(map(str,ans))):
    ans += 1
  else:
    print(ans)
    break

### FIXED CODE ###

N,K = map(int,input().split())
D = set(map(int,input().split()))
ans = N
while(True):
  if any([i in D for i in list(map(int,str(ans)))]):
    ans += 1
  else:
    print(ans)
    break
S = input()
w = S.split('B')
w.remove('')
b = S.split('W')
b.remove('')

print(len(w)+len(b)-1)

### FIXED CODE ###

S = input()
w = S.split('B')
w = [x for x in w if x != '']
b = S.split('W')
b = [x for x in b if x != '']

print(len(w)+len(b)-1)
import fraction

N,X = map(int,input().split())
x = [int(i) for i in input().split()]
ans = abs(X-x[0])
now = X
for i in x:
    if abs(now - i) % ans:
        ans = fraction.gcd(ans, abs(now-i))
    now = i

print(ans)

### FIXED CODE ###

def gcd(a,b):
    while b:
        a, b = b, a % b
    return a
N,X = map(int,input().split())
x = [int(i) for i in input().split()]
ans = abs(X-x[0])
now = X
for i in x:
    if abs(now - i) % ans:
        ans = gcd(ans, abs(now-i))
    now = i

print(ans)
n, r = map(int, input().split())
 
if n < 10:
	print(r + 100*(10-k))
else:
    print(r)

### FIXED CODE ###

n, r = map(int, input().split())
 
if n < 10:
	print(r + 100*(10-n))
else:
    print(r)
l = input()
m = input()
z = l.split(' ')
M = int(z[1])
N = int(z[0])
C = (1/(4*M))*N
F = m.split(' ')
X = []
for item in f:
	votes = int(item)
	X.append(votes)
X.sort(reverse = True)
for i in range(M):
	if X[i]<C:
		print("No")
		return
print("Yes")

### FIXED CODE ###

l = input()
m = input()
z = l.split(' ')
M = int(z[1])
N = int(z[0])
F = m.split(' ')
X = []
 
for item in F:
  votes = int(item)
  X.append(votes)

S = sum(X)
C = (S/(4*M))
X.sort(reverse=True)
if X[M-1]<C:
  print("No")
else:
  print("Yes")
#import sys
#input=sys.stdin.readline

s=input()
ans=0

for i in range(2 ** (len(s)-1)):
  bin_i = bin(i)[2:].rjust(len(s)-1,"0")
  li=[]
  n=s[0]
  #0がなし、1が+
  for ix,sign in enumerate(bin_i):
    if sign=="0":
      n+=s[ix+1]
    else:
      li.append(int(n))
      n=s[ix+1]
  li.append(int(n))
  ans+=sum(li)

print(ans)

### FIXED CODE ###

s=input()
ans=0

if len(s)==1:
  print(s)
  exit()

for i in range(2 ** (len(s)-1)):
  bin_i = bin(i)[2:].rjust(len(s)-1,"0")
  li=[]
  n=s[0]
  for ix,sign in enumerate(bin_i):
    if sign=="0":
      n+=s[ix+1]
    else:
      li.append(int(n))
      n=s[ix+1]
  li.append(int(n))
  ans+=sum(li)

print(ans)
t=int(input().split())
l=[1,0,-1]
k=t[3]
s=0
i=0
while(k!=0):
  if(k>t[i]):
    s+=l[i]*t[i]
    k-=t[i]
  else:
    s+=l[i]*k
    k=0
  i+=1
print(s)

### FIXED CODE ###

t=list(map(int,input().split()))
l=[1,0,-1]
k=t[3]
s=0
i=0
while(k!=0):
  if(k>t[i]):
    s+=l[i]*t[i]
    k-=t[i]
  else:
    s+=l[i]*k
    k=0
  i+=1
print(s)
X,Y,A,B,C=map(int,input().split())
p=sorted(map(int,input().split()))
q=sorted(map(int,input().split()))
r=sorted(map(int,input().split()))
ans=[]
ans+=p[A-X:]
ans+=q[B-Y:]
ans.sort()
i=0
j=0
for i in ans:
	j=max(r)
	if i<j:
		ans[i]=r.pop()
print(sum(ans))



### FIXED CODE ###

X,Y,A,B,C=map(int,input().split())
p=sorted(map(int,input().split()))
q=sorted(map(int,input().split()))
r=sorted(map(int,input().split()))
ans=[]
ans+=p[A-X:]
ans+=q[B-Y:]
ans.sort()
j=0
k=0
for i in ans:
	if len(r)>1:
		k=r[-1]
	elif len(r)==1:
		k=r[0]
	else:
		break
	if i<k:
		ans[j]=r.pop()
		j+=1
	else:
		break
print(sum(ans))
N=int(input())
a=[]
for i in range(N):
	a.append(input())
d={}
sor={}
for i in range(N):
    if a[i] in d.keys():
        d[a[i]]+=1
    else:
        d.setdefault(a[i],1)
sod = sorted(d.keys())
#max=sod["a[0]"]
maxval=0
for i in range(N):
    if maxval<=d[a[i]]:
        maxval=d[a[i]]
for i in range(N):
    if maxval==d[sod[i]]:
        print(sod[i])

### FIXED CODE ###

N=int(input())
a=[]
b=0
for i in range(N):
	a.append(input())
d={}
sor={}
for i in range(N):
    if a[i] in d.keys():
        d[a[i]]+=1
    else:
        d.setdefault(a[i],1)
        b+=1
sod = sorted(d.keys())
#max=sod["a[0]"]
maxval=0
for i in range(N):
    if maxval<=d[a[i]]:
        maxval=d[a[i]]
for i in range(b):
    if maxval==d[sod[i]]:
        print(sod[i])
money=int(input())
sum=int(input())
money500=500*money
if money500>=sum:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

money,sum=map(int,input().split())
money500=500*money
if money500>=sum:
    print('Yes')
else:
    print('No')
N, K = map(int, input().split())
lst = []
for _ in range(N):
    lst.append(int(input()))
lst = sorted(lst)
ret = 100000000000
 
for idx, x in enumerate(lst[:-K+1], 0):
    tmp = lst[idx + K-1] - x
    if tmp < ret:
        ret = tmp
print(ret)

### FIXED CODE ###

D = int(input())
lst = ['Christmas'] + ['Eve'] * (25 - D)
print(' '.join(lst))
n = int(input())

if n % 2 == 0:
    n += 1
while not is_prime(n):
    n += 2
print(n)

def is_prime(q):
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    for i in xrange(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

### FIXED CODE ###

def is_prime(n):
    if n == 1:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

if __name__ == '__main__':
    n = int(input())
    while not is_prime(n):
        n += 1
    print(n)
N = input()
a = map(int, raw_input().split())

if max(a)-min(a)>=2:
  print "No"
elif max(a)-min(a)==0:
  if N>=2*a[0] or N==a[0]+1:
    print "Yes"
  else:
    print "No"
else:
  if a.count(max(a))>=2 and a.count(min(a))==min(a):
    print "Yes"
  else:
    exit(-1)
    print "No"


### FIXED CODE ###

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

if max(a)-min(a)>=2:
  print "No"
elif max(a)-min(a)==0:
  if N>=2*a[0] or N==a[0]+1:
    print "Yes"
  else:
    print "No"
else:
  cn = max(a)-a.count(min(a))
  if a.count(max(a))>=2 and cn>0 and N>=a.count(min(a))+2*cn:
    print "Yes"
  else:
    print "No"
x = int(input())
if x >= 30:
  print("YES")
 else:
  print("NO")

### FIXED CODE ###

x = int(input())
if x >= 30:
  print("Yes")
else:
  print("No")
s = input().split()
A = s[0]
B = s[1]

if A<=9 and B<=9:
  print(A*B)
else:
  print(-1)

### FIXED CODE ###

i = list(map(int, input().split()))
 #出力：['s_1', 's_2']
A=i[0] #出力：s_1
B=i[1] #出力：s_2

if A<=9 and B<=9:
  print(A*B)
else:
  print(-1)
import sys

	p = 0

	args = sys.argv
	n = int(args[1])
	for i in range(1, n+1):
		if i % 2 == 1:
			p = p + 1
	
	print(p/n)

### FIXED CODE ###

import sys

def main():

	p = 0

	args = sys.argv
	n = int(input())
	
	print((int(n/2) + n%2 )/n)

if __name__ == "__main__":
    main()
H = int(input())

cnt = 0
ans = 0

while H >= 1:
    H = H / 2
    if cnt == 0:
        cnt += 1
        ans += 1
    else:
        ans += cnt * 2
        cnt = cnt * 2

print(ans)


### FIXED CODE ###

H, A = map(int, input().split())

cnt = 0

while H > 0:
    H = H - A
    cnt += 1
print(cnt)
a,b,c = input().split()

if a == b == c:
  print(Yes)
else:
  print(No)


### FIXED CODE ###

a,b,c = map(int,input().split())

if a == b and b == c:
  print("No")
elif a != b and b != c and a != c:
  print("No")
else:
  print("Yes")
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
dic={}
for i in range(m):
  b,c=map(int,input().split())
  if c in dic:
    dic[c]+=b
  else:
    dic[c]=b
ol=sorted(dic.items(), reverse=True, key=lambda x:x[0])
index=0
loopstop=False
for li in ol:
  for i in range(li[1]):
    if li[0]>a[index]:
      a[index]=li[0]
      index+=1
    else:
      loopstop=True
      break;
  if loopstop or index>=n :
    break
print(sum(a))

### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
dic={}
for i in range(m):
  b,c=map(int,input().split())
  if c in dic:
    dic[c]+=b
  else:
    dic[c]=b
ol=sorted(dic.items(), reverse=True, key=lambda x:x[0])
index=0
loopstop=False
for li in ol:
  for i in range(li[1]):
    if li[0]>a[index]:
      a[index]=li[0]
      index+=1
      if index>=n:
        loopstop=True
        break;
    else:
      loopstop=True
      break;
  if loopstop:
    break
print(sum(a))
s = int(input())

n = len(s)

for i in range(n-1):
  if s[i] == s[i+1]:
    if s[i] == 0:
      s[i+1] = 1
    else:
      [i] = 0

print(s)

### FIXED CODE ###

s = list(map(int,input()))

n = len(s)
 
ans_l = 0
for i in range(n-1):
  if s[i] == s[i+1]:
    ans_l += 1
    if s[i] == 0:
      s[i+1] = 1
    else:
      s[i+1] = 0
print(ans_l)
n, c = list(map(int, input().split()))
sushi1 = []
sushi2 = []
c1 = []
c2 = []
c3 = []
c4 = []
k1 = 0
k2 = 0
for i in range(n):
    x, v = list(map(int, input().split()))
    sushi1.append((x, v))
    sushi2.append((c-x, v))
sushi1.sort()
sushi2.sort()
for j in range(n):
    k1 += sushi1[j][1]
    k2 += sushi2[j][1]
    c1.append(k1-sushi1[j][0])
    c2.append(k2-sushi2[j][0])
for k in range(n):
    c3.append(c1[k]+max(c2[:n-k])-sushi1[k][0])
    c4.append(c2[k]+max(c1[:n-k])-sushi2[k][0])
print(max(c1+c2+c3+c4, 0))

### FIXED CODE ###

import numpy as np
n, c = list(map(int, input().split()))
xv = list(list(map(int, input().split())) for i in range(n))
sushi1, max1, sushi2, max2 = [0], [0], [0], [0]
sum1, sum2 = 0, 0
for x, v in xv:
    sum1 += v
    sushi1.append(max(sum1 - x, sushi1[-1]))
    max1.append(max(sum1 - 2*x, max1[-1]))
for x, v in xv[::-1]:
    sum2 += v
    sushi2.append(max(sum2 - (c-x), sushi2[-1]))
    max2.append(max(sum2 - 2*(c-x), max2[-1]))
ans1 = max(np.array(sushi1) + np.array(max2[::-1]))
ans2 = max(np.array(sushi2) + np.array(max1[::-1]))
print(max(0, ans1, ans2))
L, R = map(int, input().split())
if R - L >= 2019 :
    print(0)
list = []
else :
    for i in range(L, R+1):
    k = i % 2019
    list.append(k)
    k = 0
list_sort = sorted(list())
l = list_sort[0] * list_sort[1]
print(l % 2019)


### FIXED CODE ###

L, R = map(int, input().split())
if R - L >= 2019 :
    print(0)

else :
    t = []
    for i in range(L, R):
        for j in range(i + 1, R + 1) :
            t.append((i * j) % 2019)
    print(min(t))
x=string(input())
if x=="ABC":
    print("ARC")
else:
    print("ABC")

### FIXED CODE ###

x=input()
if x=="ABC":
    print("ARC")
else:
    print("ABC")
N = input()
sum = N*(N+1)/2 
print(sum)


### FIXED CODE ###

N = input()
sum = N * (N + 1) / 2 
print(sum)
import math

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

cnt = 0
x = []
x.append(a[0])

for i in range(n-1):
    if x[i] > 0:
        if x[i]+a[i+1] > -1:
            cnt += math.fabs(x[i] + a[i+1]) + 1
            x += [-1]
        else:
            x += [x[i] + a[i+1]]
        
    else:
        if x[i]+a[i+1] < +1:
            cnt += math.fabs(x[i] + a[i+1]) + 1
            x += [1]
        else:
            x += [x[i] + a[i+1]]

print(int(cnt))

### FIXED CODE ###

x = input().split()
for _x in x:
    print(str(_x[0]).capitalize(), end="")
"""
14:07-
"""
import bisect
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N, M = list(map(int, sys.stdin.readline().split()))
A = list(map(int, sys.stdin.readline().split()))
B = list(map(int, sys.stdin.readline().split()))

MOD = 10 ** 9 + 7

A.sort()
B.sort()

if any([a == b for a, b in zip(A[:-1], A[1:])]) or any([a == b for a, b in zip(B[:-1], B[1:])]):
    # 同じのが複数ある
    print(0)
    exit()
if max(A) > N * M or max(B) > N * M:
    # 最大値が大きすぎ
    print(0)
    exit()

remains = 0
fixed = 0
ans = 1
for k in range(1, N * M + 1)[::-1]:
    # k が入る場所どこ？
    top = bisect.bisect_left(A, k)
    left = bisect.bisect_left(B, k)
    if A[top] == k and B[left] == k:
        # このマスに入れるしかない
        pattern = 1
        fixed += 1
    elif A[top] == k:
        # この行のどっか
        pattern = len(B) - left
        fixed += 1
    elif B[left] == k:
        # この列のどっか
        pattern = len(A) - top
        fixed += 1
    else:
        # どこでも OK
        couho = (len(A) - top) * (len(B) - left)
        pattern = couho - fixed
        fixed += 1
    ans *= pattern
    ans %= MOD
print(ans)


### FIXED CODE ###

"""
14:07-
"""
import bisect
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N, M = list(map(int, sys.stdin.readline().split()))
A = list(map(int, sys.stdin.readline().split()))
B = list(map(int, sys.stdin.readline().split()))

MOD = 10 ** 9 + 7

A.sort()
B.sort()

if any([a == b for a, b in zip(A[:-1], A[1:])]) or any([a == b for a, b in zip(B[:-1], B[1:])]):
    # 同じのが複数ある
    print(0)
    exit()
if max(A) != N * M or max(B) != N * M:
    # 最大値がおかしい
    print(0)
    exit()

fixed = 0
ans = 1
top = len(A) - 1
left = len(B) - 1
for k in range(1, N * M + 1)[::-1]:
    # k が入る場所どこ？
    while top - 1 >= 0 and A[top - 1] >= k:
        top -= 1
    while left - 1 >= 0 and B[left - 1] >= k:
        left -= 1
    top = bisect.bisect_left(A, k)
    left = bisect.bisect_left(B, k)
    if A[top] == k and B[left] == k:
        # このマスに入れるしかない
        pattern = 1
        fixed += 1
    elif A[top] == k:
        # この行のどっか
        pattern = len(B) - left
        fixed += 1
    elif B[left] == k:
        # この列のどっか
        pattern = len(A) - top
        fixed += 1
    else:
        # どこでも OK
        pattern = (len(A) - top) * (len(B) - left) - fixed
        fixed += 1
    ans *= pattern
    ans %= MOD
print(ans)
s = input().split()
nums = []
[[nums.append(num) for num in row] for row in s[:3]]
n = int(s[3])
bs = s[4:]
mat = [num in bs for num in nums]
patterns = [[1, 2, 3],
            [1, 5, 9],
            [1, 4, 7],
            [2, 5, 8],
            [3, 5, 7],
            [3, 6, 9],
            [4, 5, 6],
            [7, 8, 9]]
for pat in patterns:
    if mat[pat[0]] and mat[pat[1]] and mat[pat[2]]:
        print("Yes")


### FIXED CODE ###

import sys
input = sys.stdin.readlines()
nums = []
[[nums.append(num) for num in row.strip().split(" ")] for row in input[:3]]
bs = [i.strip() for i in input[4:]]
mat = [num in bs for num in nums]
patterns = [[0, 1, 2],
            [0, 4, 8],
            [0, 3, 6],
            [1, 4, 7],
            [2, 4, 6],
            [2, 5, 8],
            [3, 4, 5],
            [6, 7, 8]]
for pat in patterns:
    if mat[pat[0]] and mat[pat[1]] and mat[pat[2]]:
        print("Yes")
        sys.exit()
print("No")
import numpy as np
N = int(input())
h_array = np.array(list(map(int, input().split()))).reshape(-1)


def cost_diff(num, span, given_array):
    diff_val = np.abs(given_array[num] - given_array[num - span])
    return diff_val


dp = [[] for i in range(N)]
diff_ini = cost_diff(1, 1, h_array)

for i in range(N):
    if i == 0:
        dp[0].append(0)
    elif i == 1:
        dp[1].append(min(dp[0] + diff_ini))
    else:
        tmp_1 = dp[i - 1] + cost_diff(i, 1, h_array)
        tmp_2 = dp[i - 2] + cost_diff(i, 2, h_array)
        tmp = np.min(tmp_1, tmp_2)
        dp[i].append(tmp)
print(dp[N - 1][0])


### FIXED CODE ###

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

dp = [10 ** 5 for i in range(N)]

for i in range(N):
    if i == 0:
        dp[0] = 0
    elif i == 1:
        dp[1] = dp[0] + abs(h_array[1] - h_array[0])
    else:
        dp[i] = min(dp[i - 1] + abs(h_array[i] - h_array[i - 1]), dp[i - 2] + abs(h_array[i] - h_array[i - 2]))
print(dp[N - 1])
# coding: utf-8
# Here your code !
a = input()
b = input()
x = a*b
y = a*2 + b*2
print "%d"%x,
print "%d"%y

### FIXED CODE ###

# coding: utf-8
# Here your code !
a,b = input().split()
m = int(a) * 2 + int(b) * 2
s = int(a) * int(b)
print(s,m)
def main():
    H, W = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    
    left = [[-1]*W]*H
    right = [[-1]*W]*H
    up = [[-1]*W]*H
    down = [[-1]*W]*H

    for i in range(H):
        for j in range(W):
            if S[i][j] == '.':
                if j == 0:
                    left[i][j] = 0
                else:
                    left[i][j] = left[i][j-1] + 1
                if i == 0:
                    up[i][j] = 0
                else:
                    up[i][j] = up[i-1][j] + 1
            else:
                left[i][j] = -1
                up[i][j] = -1
            
            if S[-1-i][-1-j] == '.':
                if j == 0:
                    right[-1-i][-1-j] = 0
                else:
                    right[-1-i][-1-j] = right[-1-i][-1-(j-1)] + 1
                if i == 0:
                    down[-1-i][-1-j] = 0
                else:
                    down[-1-i][-1-j] = down[-1-(i-1)][-1-j] + 1
            else:
                right[i][j] = -1
                down[i][j] = -1
                
    print(np.max(left+right+up+down) + 1)

main()

### FIXED CODE ###

def main():
    H, W = map(int, input().split())
    S = [list(input()) for _ in range(H)]

    left = [[-1]*W for _ in range(H)]
    right = [[-1]*W for _ in range(H)]
    up = [[-1]*W for _ in range(H)]
    down = [[-1]*W for _ in range(H)]

    for i in range(H):
        for j in range(W):
            if S[i][j] == '.':
                if j == 0:
                    left[i][j] = 0
                else:
                    left[i][j] = left[i][j-1] + 1

    for i in range(H):
        for j in range(W):
            if S[-1-i][-1-j] == '.':        
                if j == 0:
                    right[-1-i][-1-j] = 0
                else:
                    right[-1-i][-1-j] = right[-1-i][-1-(j-1)] + 1

    for i in range(H):
        for j in range(W):
            if S[i][j] == '.':
                if i == 0:
                    up[i][j] = 0
                else:
                    up[i][j] = up[i-1][j] + 1

    for i in range(H):
        for j in range(W):
            if S[-1-i][-1-j] == '.':
                if i == 0:
                    down[-1-i][-1-j] = 0
                else:
                    down[-1-i][-1-j] = down[-1-(i-1)][-1-j] + 1
            
    ans = 0
    temp = [0] * W
    for i in range(H):
        for j in range(W):
            temp[j] = left[i][j] + right[i][j] + down[i][j] + up[i][j] + 1
        ans = max(ans, max(temp))
    print(ans)

main()
import numpy as np

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

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

            
def judge(x, lst):

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

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

### FIXED 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 = -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 += BIT.sum(Binary_sorted[b]) + (b >= 0)
        BIT.add(Binary_sorted[b], 1)
 
    if inversion >= ceil((N * (N + 1) / 2) / 2):
        lo = X
    else:
        hi = X
 
print(lo)
N = int(input())
X = []
U = []
for i in range(N):
    I = input().split()
    (x, u) = (int(I[0]), I[1])
    X[i] = x
    U[i] = u

otoshidama = 0.0

for i in range(N):
    if U[i] == "JPY":
        otoshidama += X[i]
    elif U[i] == "BTC":
        otoshidama += X[i] * 380000.0

print(otoshidama)

### FIXED CODE ###

S = input()
S_split = S.split("/")
(year, month, day) = (int(S_split[i]) for i in range(3))

if month > 4:
    print("TBD")

else:
    print("Heisei")
H, W = map(int, input().split())
s_list = []
for i in range(W):
    s_list.append(input())
cnt = 0
for i in range(H):
    for j in range(1, W):
        if s_list[i][j] == '#' and s_list[i][j-1] != '#' and\
           s_list[i-1][j] != '#' and s_list[i][j+1] !='#' and\
                                                       s_list[i+1][j] != '#':
            cnt += 1
if cnt == 0:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

h, w = map(int, input().split())
s = ['.' * (w+2)] + ['.' + input() + '.' for _ in [0]*h] + ['.' * (w+2)]
a = 'Yes'
for i in range(1, h+1):
    for j in range(1, w+1):
        if s[i][j] == '#':
            if s[i-1][j] == '.' and s[i+1][j] == '.' and s[i][j-1] == '.' and\
               s[i][j+1] == '.':
                a = 'No'
print(a)
n = int(input())
A = list(map(int, input().split()))

cnt = 0
while all(a % 2 == 0 for i in A):
  A = [a / 2 for a in A]
  cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
nums = list(map(int, input().split()))
cnt = 0
while all(num % 2 == 0 for num in nums):
    nums = [num / 2 for num in nums]
    cnt += 1
print(cnt)