Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

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

for _ in range(M):
	a = A.pop()
	a = a >> 1
	for i in range(len(A)):
		if A[i] > a:
			A.insert(i, a)
			break
	else:
		A.append(a)
			

sum = 0
for a in A: sum += a
print(sum)

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
h = []

for a in A: heapq.heappush(h, -a)
for _ in range(M):
	a = heapq.heappop(h) * -1
	a //= 2
	heapq.heappush(h, -a)

sum = 0
for _ in range(N): 
	sum -= heapq.heappop(h)
print(sum)
### BUGGY CODE ###

import sys
from collections import defaultdict
sys.setrecursionlimit(10**9)

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

graph = defaultdict(list)
for _ in range(n-1):
    p,c = list(map(int, input().split()))
    graph[p].append(c)
    graph[c].append(p)

counter = defaultdict(int)
for _ in range(q):
    i,c = list(map(int, input().split()))
    counter[i] += c

ans = [0] * (n + 1)
visit = [False] * (n + 1)
def dfs(node, total_counter):
    visit[node] = True
    total_counter += counter.get(node, 0)
    
    for child in graph[node]:
        if not visit[child]:
            dfs(child, total_counter)
    ans[node] = total_counter

dfs(1, 0)

print(*ans[1:])

### FIXED CODE ###

import sys
from collections import defaultdict
sys.setrecursionlimit(10**9)

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

graph = defaultdict(list)
for _ in range(n-1):
    p,c = list(map(int, input().split()))
    graph[p].append(c)
    graph[c].append(p)

counter = defaultdict(int)
for _ in range(q):
    i,c = list(map(int, input().split()))
    counter[i] += c

ans = [0] * (n + 1)
visit = [False] * (n + 1)
def dfs(node, total_counter):
    visit[node] = True
    total_counter += counter.get(node, 0)
    
    for child in graph[node]:
        if not visit[child]:
            dfs(child, total_counter)
    ans[node] = total_counter

dfs(1, 0)

print(*ans[1:])
### BUGGY CODE ###

n = int(input())
li = list(map(int,input().split()))
lians = []
for i in range(1,n):
    lians.append(li.count(i))
lians.append(0)
for i in range(n):
    print(lians[i])

### FIXED CODE ###

n = int(input())
li = [0]*n
li1 = list(map(int,input().split()))
for i in range(n-1):
    li[li1[i]-1] += 1
for i in range(n):
    print(li[i])
### BUGGY CODE ###

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

ad = dict((i, a.count(i)) for i in set(a))

ans = 0
for v in ad.values():
    ans += v*(v-1)//2

for i in range(n):
    v = ad[a[i]]
    print(ans-v*(v-1)//2+(v-1)*(v-2)//2)

### FIXED CODE ###

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

ad = {}
for i in range(n) :
    if a[i] in ad :
        ad[a[i]] += 1
    else :
        ad[a[i]] = 1

ans = 0
for v in ad.values():
    ans += v*(v-1)//2

for i in range(n):
    v = ad[a[i]]
    print(ans-v*(v-1)//2+(v-1)*(v-2)//2)
### BUGGY CODE ###

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

mod = (10**9) +7

ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        t = (lis[i]*lis[j])
        ans += t

print(ans%mod)

### FIXED CODE ###

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

mod = 10**9+7

s = sum(lis)
tmp = 0
for i in lis:
    tmp += i**2

print(((s*s - tmp)//2) % mod)
### BUGGY CODE ###

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

mod = 10**9 + 7

ans = 0
for i in range(0, N - 1):
    for j in range(i + 1, N):
        # print(bin(A[i] ^ A[j]))
        # ans += int(bin(A[i] ^ A[j]), 0)
        ans += A[i] ^ A[j]
        ans %= mod
print(ans)


### FIXED CODE ###

import sys
import numpy as np

input = sys.stdin.buffer.readline
N = int(input())
A = np.array(list(map(int, input().split())))

MOD = 10**9 + 7

answer = 0
for n in range(63):
    B = (A >> n) & 1
    x = np.count_nonzero(B)
    y = N - x
    x *= y
    for _ in range(n):
        x = x * 2 % MOD
    answer += x
answer %= MOD
print(answer)
### BUGGY CODE ###

N, K = map(int,input().split())
P = list(map(float,input().split()))
anss=0        
for i in range(N-K+1):
    #print(i)
    ans_kari = sum([(P[i+j]+1.0)/2.0 for j in range(0,K)])
    #print(ans_kari)
    #print(i)
    if ans_kari > anss:
        anss = ans_kari

print(anss)

### FIXED CODE ###

N, K = map(int,input().split())
P = list(map(float,input().split()))
for i in range(N):
    P[i] = (P[i]+1.0)/2.0

anss=0        
for i in range(N-K+1):
    #print(i)
    #ans_kari = sum(P[i:i+K])
    if i==0:
        ans_kari = sum(P[i:i+K])
    else:
        ans_kari = ans_kari - P[i-1] + P[i+K-1]
    #print(ans_kari)
    #print(i)
    if ans_kari > anss:
        anss = ans_kari

print(anss)
### BUGGY CODE ###

import sys

input = sys.stdin.readline

INF = float("inf")


def main():
    H, N = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())

    dp = [INF] * (H + max(A))
    dp[0] = 0
    for h in range(H):
        for a, b in zip(A, B):
            dp[h+a] = min(dp[h+a], dp[h]+b)
    ans = min(dp[H:])
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

input = sys.stdin.readline

INF = float("inf")


def main():
    H, N = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())

    dp = [INF] * (H + max(A))
    dp[0] = 0
    for h in range(H):
        for a, b in zip(A, B):
            if dp[h]+b < dp[h+a]:
                dp[h+a] = dp[h]+b
    ans = min(dp[H:])
    print(ans)


if __name__ == "__main__":
    main()
### BUGGY CODE ###


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

    dp = [-1] * n
    dp[0] = 0
    for i in range(n):
        lmt = min(i+k+1,n)
        for j in range(i+1,lmt):
            tmp = dp[i] + abs(h[i]-h[j])
            if dp[j] == -1 or dp[j] > tmp:
                dp[j] = tmp
    print(dp[n-1])
    
if __name__=='__main__':
    main()


### FIXED CODE ###


def main():
    n,k=map(int,input().split())
    h=list(map(int,input().split()))
    dp=[None]*n
    temp=[1001]*n
    dp[0]=0
    dp[1]=abs(h[1]-h[0])
    for i in range(2,n):
        low=i-k-1
        if low<0:
            low=-1
        for j in range(i-1,low,-1):
            temp[j]=dp[j]+abs(h[i]-h[j])
            if j==i-1:
                mn=temp[j]
            else:
                if mn > temp[j]:
                    mn=temp[j]
        # temp2=dp[i-2]+abs(h[i]-h[i-2])
        # temp1=dp[i-1]+abs(h[i]-h[i-1])
        dp[i]=mn
        #temp=[1001]*n
    print(dp[n-1])

if __name__=='__main__':
    main()
### BUGGY CODE ###

import itertools
import operator

N, K = [int(x) for x in input().split(" ")]
A = [int(x) for x in input().split(" ")]

pro = [1] + list(itertools.accumulate(A, func=operator.mul))

for i in range(K + 1, N + 1):
    if pro[i] * pro[i - K - 1] > pro[i - K] * (pro[i - 1]):
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

N, K = [int(x) for x in input().split(" ")]
A = [int(x) for x in input().split(" ")]


for i in range(K, N):
    if A[i - K] < A[i]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import bisect

def main():
    N = int(input())
    L = list(map(int, input().split()))
    L = sorted(L)

    ans = 0

    for i in range(N):
        for j in range(i+1, N):
            X = L[i] + L[j]
            l = bisect.bisect_left(L, X, lo=j+1)
            ans += (l-(j+1))
            #print(L[j + 1:l])
    print(ans)
    return 0

if __name__ == '__main__':
    main()


### FIXED CODE ###

import bisect

def main():
    N = int(input())
    L = list(map(int, input().split()))
    L = sorted(L)

    ans = 0

    for i in range(N):
        for j in range(i+1, N):
            X = L[i] + L[j]
            l = bisect.bisect_left(L, X, lo=j+1)
            ans += (l-(j+1))
            #print(L[j + 1:l])
    print(ans)
    return 0

if __name__ == '__main__':
    main()
### BUGGY CODE ###

N = int(input())
S = input()

result = min(S.count("."),S.count("#"))
i = 0

while i < N:
    leftslice = S[:i]
    rightslice = S[i:]
    leftblack = leftslice.count("#")
    rightwhite = rightslice.count(".")
    nowresult = leftblack + rightwhite
    if result >= nowresult:
        result = nowresult
    else:
        i += (nowresult - result)
    i += 1

print(result)

### FIXED CODE ###

N = int(input())
S = input()
 
result = min(S.count("."),S.count("#"))
leftblack = 0
rightwhite = S.count(".")
 
for i in range(N):
    if(S[i] == "."):
        rightwhite -= 1
    else:
        leftblack += 1
    if result >= leftblack + rightwhite:
        result = leftblack + rightwhite
 
print(result)
### BUGGY CODE ###

R,G,B,N=map(int,input().split())
ans=0
for i in range(N//R + 1):
  for j in range(N//G + 1):
    if R*i+G*j <= N:
      if (N - (R*i+G*j))%B==0:
        ans+=1
print(ans)

### FIXED CODE ###

R,G,B,N=map(int,input().split())
ans=0
for i in range(N//R + 1):
  for j in range(N//G + 1):
    if R*i+G*j <= N:
      if (N - (R*i+G*j))%B==0:
        ans+=1
print(ans)
### BUGGY CODE ###

n,m= map(int,input().split())
A =[list(map(str,input().split())) for _ in range(m)]
B = []
C = []
ans = 0
pna = 0
for i in range(m):
    if A[i][1]=="AC":
        if A[i][0] not in B :
            B.append(A[i][0])
            ans += 1
            pna += C.count(A[i][0])
    if A[i][1]=="WA"  :
        C.append(A[i][0])
print(ans,pna)
        

### FIXED CODE ###

N,M = [int(x) for x in input().split()]
count = [0]*N
ac = 0
wa = 0
ireta = []
for i in range(M):
    a,b = input().split()
    a = int(a)
    if b == "AC" and count[a-1] == 0:
        count[a-1] = 1
        ac += 1
    elif count[a-1] == 0:
        ireta.append(a)
        wa += 1
for i in range(len(ireta)):
    if count[ireta[i]-1] == 0:
        wa -= 1
print(ac,wa)
### BUGGY CODE ###

A,B,C,K = map(int,input().split())
N = [A,B,C]
N2 = N.copy()
if A == B == C:
    print(0)
else:
    for i in range(K):
        N2[0] = N[1] + N[2]
        N2[1] = N[0] + N[2]
        N2[2] = N[0] + N[1]
        N = N2.copy()
    ans = N2[0] - N2[1]
    if abs(ans) > 10**18:
        print('Unfair')
    else:
        print(ans)

### FIXED CODE ###

a,b,c,k = map(int, input().split())
cheak = 10**18
ans = a-b
def calc(a,b,c,k):
    if a == b:
        return 0
    elif ans < 0:
        if k % 2 == 1:
            return -ans
        else:
            return ans
    else:
        if k % 2 == 1:
            return -ans
        else:
            return ans
ans_n = calc(a,b,c,k)
if ans_n > cheak:
    print("Unfair")
else:
    print(ans_n)
### BUGGY CODE ###

n, m = map(int, input().split())
A = list(map(int, input().split()))
for _ in range(m):
    b, c = map(int, input().split())
    for i in range(b):
        A.append(c)

A = sorted(A, reverse=True)
result = [A[i] for i in range(n)]
print(sum(result))

### FIXED CODE ###

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(m)]
BC.sort(key=lambda x: -x[1])

maxi = n*2
extend = A.extend
[extend([ls[1]] * ls[0]) for ls in BC if len(A) <= maxi]
A.sort(reverse=True)

print(sum(A[:n]))
### BUGGY CODE ###

import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from bisect import bisect_right

n, m = li()
lrc = [list(li()) for _ in range(m)]

# n = 10**5
# m = 10**5
# lrc = [[1, n, 5] for _ in range(m)]

# l -> r の降順にソート
lrc = sorted(lrc, key=lambda x: x[2])
lrc = sorted(lrc, key=lambda x: x[1])
lrc = sorted(lrc, key=lambda x: x[0])
#lrc = sorted((sorted(lrc, key=lambda x: x[1])), key=lambda x: x[0])

# 二分探索で距離更新
INF = float('inf')
dist = [INF]*n
dist[0] = 0

for left_idx, right_idx, ci in lrc:
    left_idx -= 1
    newleft_idx = bisect_right(dist, dist[left_idx] + ci)
    for idx in range(newleft_idx, right_idx):
        dist[idx] = dist[left_idx] + ci

if dist[-1] == INF:
    print(-1)
else:
    print(dist[-1])


### FIXED CODE ###

import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from bisect import bisect_right

n, m = li()
lrc = [list(li()) for _ in range(m)]

# n = 10**5
# m = 10**5
# lrc = [[1, n, 5] for _ in range(m)]

# l -> r の降順にソート
lrc = sorted(lrc, key=lambda x: x[2])
lrc = sorted(lrc, key=lambda x: x[1])
lrc = sorted(lrc, key=lambda x: x[0])
#lrc = sorted((sorted(lrc, key=lambda x: x[1])), key=lambda x: x[0])

# 二分探索で距離更新
INF = float('inf')
dist = [INF]*n
dist[0] = 0

for left_idx, right_idx, ci in lrc:
    left_idx -= 1
    newleft_idx = bisect_right(dist, dist[left_idx] + ci)
    for idx in range(newleft_idx, right_idx):
        dist[idx] = dist[left_idx] + ci

if dist[-1] == INF:
    print(-1)
else:
    print(dist[-1])
### BUGGY CODE ###

s = input()
ans = 0
while(True):
  zero_one = s.count("01")
  one_zero = s.count("10")
  if(zero_one == 0 and one_zero == 0):
    break
  if(zero_one > one_zero):
    ans += zero_one
    s = s.replace('01',"")
  else:
    ans += one_zero
    s = s.replace('10',"")
print(ans*2)

### FIXED CODE ###

s = input()
print(2 * min([s.count("0"), s.count("1")]))
### BUGGY CODE ###

s=int(input())
e_list=list(map(int,input().split()))
e_dic={}
for i in range(1,s+1):
  e_dic[i]=e_list.count(i)

for i in e_dic.keys():
  print(e_dic[i])

### FIXED CODE ###

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

ans=[0]*n

for i in l:
    ans[i-1]+=1

for j in ans:
    print(j)
### BUGGY CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**7)


def BFS(s):
    color=["white" for _ in range(n)]
    D=[float("inf") for _ in range(n)]

    color[s-1]="gray"
    D[s-1]=0
    queue=deque([s-1])

    while len(queue)!=0:
        u=queue.popleft()
        for i in M[u]:
            if color[i]=="white":
                color[i]="gray"
                D[i]=D[u]+1
                queue.append(i)
        color[u]="black"

    return D


n,x,y=map(int,input().split())

M=[[] for _ in range(n)]
for i in range(n-1):
    M[i].append(i+1)
    M[i+1].append(i)
M[x-1].append(y-1)
M[y-1].append(x-1)

C=[0]*n
for i in range(n):
    for j in BFS(i+1)[i:]:
        C[j] +=1

for i in C[1:]:
    print(i)

### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**7)


def BFS(s):
    color=["white" for _ in range(n)]
    D=[float("inf") for _ in range(n)]

    color[s-1]="gray"
    D[s-1]=0
    queue=deque([s-1])

    while len(queue)!=0:
        u=queue.popleft()
        for i in M[u]:
            if color[i]=="white":
                color[i]="gray"
                D[i]=D[u]+1
                queue.append(i)
        color[u]="black"

    return D


n,x,y=map(int,input().split())

M=[[] for _ in range(n)]
for i in range(n-1):
    M[i].append(i+1)
    M[i+1].append(i)
M[x-1].append(y-1)
M[y-1].append(x-1)

C=[0]*n
for i in range(n):
    for j in BFS(i+1)[i:]:
        C[j] +=1

for i in C[1:]:
    print(i)
### BUGGY CODE ###

import math
import itertools
import numpy as np
list2 = []
result = 0
n = int(input())
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
#            list2.append([i,j,k])
            result +=  np.gcd.reduce((i,j,k))
print(result)

### FIXED CODE ###

from math import gcd
ans = 0
k = int(input())
for i in range(1, k+1):
	for j in range(1, k+1):
		for l  in range(1, k+1):
			ans += gcd(gcd(i, j), l)
print(ans)
### BUGGY CODE ###

#n=int(input())
#li=input().split()
#d=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
#import math
#import numpy as np

lis=[]
#N Q
li=list(map(int,input().split()))
S=input()
for i in range(li[1]):
    #l_i r_i
    lr=list(map(int,input().split()))
    lis.append(lr)
for i in range(li[1]):
    ans=0
    for j in range(lis[i][1]-lis[i][0]):
        if S[lis[i][0]+j-1:lis[i][0]+j+1]=="AC":
            ans+=1
    print(ans)


### FIXED CODE ###

#n=int(input())
#li=input().split()
#d=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
#import numpy as np
#import math

lis=[]
#N Q
li=list(map(int,input().split()))
S=input()
for i in range(li[1]):
    #l_i r_i
    lr=list(map(int,input().split()))
    lis.append(lr)
L=[0]*(li[0])
for i in range(li[0]-1):
    L[i+1]+=L[i]
    if S[i:i+2]=="AC":
        L[i+1]+=1
for i in range(li[1]):
    print(L[lis[i][1]-1]-L[lis[i][0]-1])
### BUGGY CODE ###

# https://cs.stackexchange.com/questions/93030/algorithm-for-checking-if-a-list-of-integers-is-pairwise-coprime

import math
n = int(input())
nums = list(map(int, input().split()))

gcd_ = nums[0]
for num in nums[1:]:
    gcd_ = math.gcd(gcd_, num)

if gcd_ >= 2:
    print('not coprime')
    exit()



def smallest_divisor(num, start):
    if num == 1:
        raise ValueError("error!")
    d = start
    while d * d <= num:
        if num % d == 0:
            return d
        d += 1
    return num


prime_set = set()

for num in nums:
    if num == 1:
        continue

    soinsuu = set()
    
    warareru = num
    start = 2
    while True:
        divi = smallest_divisor(warareru, start)
        soinsuu.add(divi)
        warareru = warareru // divi
        start = divi
        if warareru == 1:
            break
    # print(soinsuu)
    if soinsuu & prime_set:
        print('setwise coprime')
        exit()
    else:
        prime_set |= soinsuu

print('pairwise coprime')


### FIXED CODE ###

# https://cs.stackexchange.com/questions/93030/algorithm-for-checking-if-a-list-of-integers-is-pairwise-coprime

import math
n = int(input())
nums = list(map(int, input().split()))

gcd_ = nums[0]
for num in nums[1:]:
    gcd_ = math.gcd(gcd_, num)

if gcd_ >= 2:
    print('not coprime')
    exit()



def smallest_divisor(num, start):
    if num == 1:
        raise ValueError("error!")
    d = start
    while d * d <= num:
        if num % d == 0:
            return d
        d += 1
    return num


prime_set = set()

for num in nums:
    if num == 1:
        continue

    soinsuu = set()
    
    warareru = num
    start = 2
    while True:
        divi = smallest_divisor(warareru, start)
        soinsuu.add(divi)
        warareru = warareru // divi
        start = divi
        if warareru == 1:
            break
    # print(soinsuu)
    if soinsuu & prime_set:
        print('setwise coprime')
        exit()
    else:
        prime_set |= soinsuu

print('pairwise coprime')
### BUGGY CODE ###

import math

n=int(input())

XY=[]

for i in range(n):
    x,y=map(int,input().split())
    XY.append([x,y])

v=[]

for i in range(n):
    for j in range(n):
        if j!=i:
            v.append([XY[i][0]-XY[j][0],XY[i][1]-XY[j][1]])


c=0
for vx,vy in v:
    cv=0
    for i in range(n):
        for j in range(n):
            if j!=i and [XY[i][0]-XY[j][0],XY[i][1]-XY[j][1]]==[vx,vy]:
                cv+=1
    c=max(cv,c)

print(n-c)

### FIXED CODE ###

import math

n=int(input())

XY=[]

for i in range(n):
    x,y=map(int,input().split())
    XY.append([x,y])

v=[]

for i in range(n):
    for j in range(n):
        if j!=i:
            v.append([XY[i][0]-XY[j][0],XY[i][1]-XY[j][1]])


c=0
for vx,vy in v:
    cv=0
    for i in range(n):
        for j in range(n):
            if j!=i and [XY[i][0]-XY[j][0],XY[i][1]-XY[j][1]]==[vx,vy]:
                cv+=1
    c=max(cv,c)

print(n-c)
### BUGGY CODE ###

N,K = map(int,input().split())

if K==1:
  print(0)
  exit()
  
s = N
for i in range(10**9):
  s = min(s,abs(N-K))
  N -= K
print(s)
  

### FIXED CODE ###

N,K = map(int,input().split())
a = N%K

print(min(a,K-a))
### BUGGY CODE ###

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

for i in range(len(x)):
    tmp_list = x.copy()
    tmp_list.pop(i)
    tmp_list.sort()
    print(tmp_list[int(n/2-1)])


### FIXED CODE ###

n = int(input())
x = list(map(int, input().split()))
sx = sorted(x)

min_mid = sx[int(n/2-1)]
max_mid = sx[int(n/2)]

for i in x:
    if i <= min_mid:    # 左半分から取られてる時
        print(max_mid)
    else:               # 右半分から取られてる時
        print(min_mid)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

# AtCoder Beginner Contest
# Problem C

if __name__ == '__main__':
    n = int(input())
    x = list(map(int, input().split()))

    for i in range(n):
        mod_x = list(x)
        tmp = mod_x.pop(i)
        mod_x = sorted(mod_x)
        print(mod_x[(n // 2) - 1])


### FIXED CODE ###

# -*- coding: utf-8 -*-

# AtCoder Beginner Contest
# Problem C

if __name__ == '__main__':
    n = int(input())
    x = list(map(int, input().split()))
    sorted_x = sorted(x)

    low = sorted_x[(n // 2) - 1]
    high = sorted_x[(n // 2)]

    for i in range(n):
        if x[i] < high:
            print(high)
        else:
            print(low)
### BUGGY CODE ###

N = int(input())
S = input()
ans = set()
for i0 in range(N - 2):
    for i1 in range(i0 + 1, N - 1):
        for i2 in range(i1 + 1, N):
            ans.add(int(S[i0] + S[i1] + S[i2]))
print(len(ans))

### FIXED CODE ###

N = int(input())
S = tuple(map(int, input()))

ans = 0
pins = [0] * 3
for pin in range(1000):
    pins[0] = pin // 100
    pins[1] = (pin % 100) // 10
    pins[2] = pin % 10
    x = 0
    for c in S:
        if c == pins[x]:
            x += 1
            if x == 3:
                ans += 1
                break
print(ans)
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
S = sum(A)
T = [0] * N
for i in range(N-1):
  c = S
  for j in range(N // 2):
    c -= 2 * A[(i+(j+1)*2) % N - 1]
  print(c, end = " ")

c = S
for j in range(N // 2):
  c -= 2 * A[(N-1+(j+1)*2) % N - 1]
print(c)

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
a = 0
for i in range(N):
  a += A[i] * (-1) ** i
b = a
print(a, end = " ")

for i in range(0, N-2):
  b = 2 * A[i] - b
  print(b, end = " ")

print(2 * A[N-2] - b)
### BUGGY CODE ###

n = int(input())
a = input().split()
b = []

for i, num in enumerate(a):
  if i%2 == 0:
    b = b + [num]
  else:
    b = [num] + b
    
if n%2 != 0:
  b = b[::-1]

print(" ".join(b))

### FIXED CODE ###

from collections import deque

n = int(input())
a = input().split()
b = deque([])
for i, num in enumerate(a):
  if n%2 == i%2:
    b.append(num)
  else:
    b.appendleft(num)
    

print(" ".join(b))
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]


def main():
    K = int(input())
    x = 0
    if K % 2 == 0 or K % 5 ==  0:
        print(-1)
    for i in range(K):
        amari = (7 * 10 ** i) % K
        x = x + amari
        if x % K == 0:
            print(i + 1)
            break
        x = x % K


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]


def main():
    K = int(input())
    x = 0
    i = 0
    if K % 2 == 0 or K % 5 ==  0:
        print(-1)
        exit()
    
    while True:
        x = (x * 10 + 7) % K
        i += 1
        if x == 0:
            print(i)
            break


    

if __name__ == "__main__":
    main()
### BUGGY CODE ###

import bisect
N=int(input())
p_list = list(map(int,input().split()))
p_list.sort()
ans = 0
for i in range(1,N-1):
  for j in range(i+1,N):
    ans+=i-bisect.bisect_right(p_list[:i],p_list[j]-p_list[i])
print(ans)

### FIXED CODE ###

import bisect
N=int(input())
l = list(map(int,input().split()))
l.sort()
ans = 0
for i in range(1,N-1):
  for j in range(i+1,N):
    m=bisect.bisect_right(l,l[j]-l[i])
    if i>m:
      ans+=i-m
print(ans)