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

import sys

n = int(sys.stdin.readline().strip())
nums = list(map(int, sys.stdin.readline().strip().split()))

d = dict()
for one in nums:
    if one in d:
        d[one] += 1
    else:
        d[one] = 1

def C(a):
    return (a*(a-1)//2 )

res_history = dict()

for one in nums:
    if one in res_history:
        print(res_history[one])
    else:
        d[one] -= 1
        res = 0
        for k,v in d.items():
            if v==2:
                res += 1
            elif v > 2:
                res += C(v)
        print (res)
        d[one] += 1
        res_history[one] = res


### FIXED CODE ###

import sys

n = int(sys.stdin.readline().strip())
nums = list(map(int, sys.stdin.readline().strip().split()))
# appear times
d = dict()
for one in nums:
    if one in d:
        d[one] += 1
    else:
        d[one] = 1

def C(a):
    return (a*(a-1)//2 )

accum = 0
for k, v in d.items():
    accum += C(v)

res_history = dict()

for one in nums:
    if one in res_history:
        print(res_history[one])
    else:
        if d[one] == 1:
            print(accum)
        else:
            res = accum 
            delta = C(d[one]) - C(d[one] - 1)
            res -= delta
            res_history[one] = res
            print(res)
### BUGGY CODE ###

# coding: utf-8
N,M=map(int,input().split())
L=[]
B=[]
flg=0
cnt=0
for i in range(M):
    a,b=list(map(int,input().split()))
    L.append([a,b])
    if a==1:
        B.append(b)
        cnt+=1
#print(L)
ans=[]
for i in range(M):
    for j in range(cnt):
        if L[i][0]==B[j]:
            ans.append(L[i][1])
#print(ans)
if N in ans:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

### FIXED CODE ###

# coding: utf-8
N,M=map(int,input().split())
L=[]
B=[]
A=[]
flg=0
cnt=0
for i in range(M):
    a,b=list(map(int,input().split()))
    L.append([a,b])
    if a==1:
        B.append(b)
        cnt+=1
    elif b==N:
        A.append(a)
        
#print(L)
ans=[]
if len(set(A)&set(B))==0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')
### BUGGY CODE ###

k,s = map(int,input().split())
total = 0
for i in range(k+1):
    for j in range(i,k+1):
        for l in range(j,k+1):
            if s == i+j+l:
                if(i == j and j == l):
                    total += 1
                elif((i == j and j != l) or (i != j and j == l) or (i == l and j != l)):
                    total += 3
                else:
                    total += 6
print(total)


### FIXED CODE ###

K,S = map(int,input().split())
cnt = 0
for i in range(K + 1):
    for j in range(K + 1):
        if i + j > S:
            continue
        elif i + j >= S - K:
            cnt += 1
print(cnt)
### BUGGY CODE ###

import string

n = int(input())

li = []
ls = []
cnt = 0
res = [[list(i) for i in string.ascii_lowercase] for _ in range(n)]
# print(res)

for i in range(n):
  s = str(input())
  sl = list(s)
#  print(s)
#  print(sl)
  li.append(sl)
  for j in range(26):
    res[i][j].append(0)

#print(res)

for i in range(n):
  for j in li[i]:
    for k in range(26):
      if res[i][k][0] == j:
        res[i][k][1] += 1
        break
        #print(res[i])

for m in range(n):
  for l in range(n):
    if l <= m:
      continue
    else:
      if res[m] == res[l]:
        cnt += 1

print(cnt)

### FIXED CODE ###

n = int(input())

l = []
cnt = 0
t = 0

for i in range(n):
    s = str(input())
    sl = ''.join(sorted(s))
    l.append(sl)

l.sort()

tmp = l[0]

for i in range(1, n):
  if tmp == l[i]:
    cnt += 1
  else:
    tmp = l[i]
    t += int(cnt * (cnt + 1) / 2)
    cnt = 0
else:
    t += int(cnt * (cnt + 1) / 2)

print(t)
### BUGGY CODE ###

# dpD - Knapsack 1
# 貰うDP
import sys
input = sys.stdin.readline

def main():
    n, w = tuple(map(int, input().rstrip().split()))
    A = tuple(tuple(map(int, input().rstrip().split())) for _ in range(n))
    dp = [0] * (w + 1)
    for i in range(n):
        for j in range(w, A[i][0] - 1, -1):
            dp[j] = max(dp[j], dp[j - A[i][0]] + A[i][1])
    print(max(dp))
    


if __name__ == "__main__":
    main()

### FIXED CODE ###

# EduDPD - Knapsack 1
import sys
input = sys.stdin.readline

n, w = list(map(int, input().rstrip().split()))
arr = [tuple(map(int, input().rstrip().split())) for _ in range(n)]
dp = [0] * (w + 1)
for i in range(n):
    for j in range(w, arr[i][0] - 1, -1):
        dp[j] = max(dp[j], dp[j - arr[i][0]] + arr[i][1])
print(max(dp))
### BUGGY CODE ###

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

Ac = 0
Bc = 0

times = 0
length = 0

while length < N:
    if times % 2 == 0:
        length += A
        Ac += 1
    else:
        length += B
        Bc += 1
    
    times += 1

if times % 2 == 0:
    print(A*Ac)
else:
    print(A*Ac - (length - N))

### FIXED CODE ###

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

div = N // (A+B)

ans = A*div

diff = N - ((A+B)*div)

if A < diff:
    ans += A
else:
    ans += diff

print(ans)
### BUGGY CODE ###

import copy

n = int(input().split()[0])
a_list = []

for _ in range(n):
    a_list.append(int(input().split()[0]))

max_list = []

for i, a in enumerate(a_list):
    kouho_list = copy.copy(a_list)
    kouho_list.pop(i)
    max_list.append(max(kouho_list))

for x in max_list:
    print(x)


### FIXED CODE ###

import copy

n = int(input().split()[0])
a_list = []

for _ in range(n):
    a_list.append(int(input().split()[0]))

kouho_list = sorted(a_list)
max_n = max(kouho_list)
second_max_n = kouho_list[-2]

max_list = [str(max_n) if x != max_n else str(second_max_n) for x in a_list]
max_str = '\n'.join(max_list)

print(max_str)
### BUGGY CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
from copy import copy

for k in range(K):
    left={}
    right={}
    for i in range(N):
        l=max(0,i-A[i])
        r=min(N-1,i+A[i])
        if l in left:
            left[l]+=1
        else:
            left[l]=1
        if r in right:
            right[r]+=1
        else:
            right[r]=1

    br=[]
    b=0
    m=N
    for i in range(N):
        if i in left:
            b+=left[i]
        br.append(b)
        m=min(m,b)
        if i in right:
            b-=right[i]
    if m==N:
        break
    A=copy(br)
print(*br)

### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
from copy import copy

for k in range(K):
    left={}
    right={}
    for i in range(N):
        l=max(0,i-A[i])
        r=min(N-1,i+A[i])
        if l in left:
            left[l]+=1
        else:
            left[l]=1
        if r in right:
            right[r]+=1
        else:
            right[r]=1

    br=[]
    b=0
    m=N
    for i in range(N):
        if i in left:
            b+=left[i]
        br.append(b)
        m=min(m,b)
        if i in right:
            b-=right[i]
    if m==N:
        break
    A=copy(br)
print(*br)
### BUGGY CODE ###

#ABC123 D
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
X,Y,Z,K = map(int, input().split())

A_list = [int(e) for e in input().split()]
B_list = [int(e) for e in input().split()]
C_list = [int(e) for e in input().split()]

delicious_list=[]
  
for i in range(X):
  for j in range(Y):
    for k in range(Z):
      delicious_list.append(A_list[i]+B_list[j]+C_list[k])
      
delicious_list.sort(reverse=True)

for i in range(K):
  print(delicious_list[i])

### FIXED CODE ###

import numpy as np
import pprint

#入力を受け付ける
X,Y,Z,K = list(map(int, input().split()))
A_list =[int(i) for i in input().split()]
B_list =[int(i) for i in input().split()]
C_list =[int(i) for i in input().split()]

#並び替え
A_list.sort(reverse=True)
B_list.sort(reverse=True)
C_list.sort(reverse=True)

#処理準備
calclated_flag = np.zeros((X,Y,Z), dtype=np.bool) #計算済みか
#calclated_result = np.zeros((X,Y,Z), dtype=np.int64) #計算結果 　…stockを使うので不要
ans = [] #解答

#木の頭
x=0
y=0
z=0
stock=[[x,y,z,A_list[x] + B_list[y] + C_list[z]]]
calclated_flag[x,y,z]=True

#ここから解答が条件の手前になるまでループ
for i in range(K):
  #stockの中から最大を調べる
  stock.sort(key=lambda x: x[3]) #ソート
  ans.append(stock[len(stock)-1][3]) #最小は一番最後。ansに追加

  temp = stock.pop() #stockから削除。
  x=temp[0]
  y=temp[1]
  z=temp[2]

  #子に分岐 ここで範囲外にならないよう判断が必要
  if x+1 <= X-1:
    if calclated_flag[x+1,y,z]!=True:
      stock.append([x+1,y,z,A_list[x+1] + B_list[y] + C_list[z]])
      calclated_flag[x+1,y,z]=True
      
  if y+1 <= Y-1:
    if calclated_flag[x,y+1,z]!=True: 
      stock.append([x,y+1,z,A_list[x] + B_list[y+1] + C_list[z]])
      calclated_flag[x,y+1,z]=True
      
  if z+1 <= Z-1:
    if calclated_flag[x,y,z+1]!=True:
      stock.append([x,y,z+1,A_list[x] + B_list[y] + C_list[z+1]])
      calclated_flag[x,y,z+1]=True
  
#回答を出力
for i in range(K):
  print(ans[i])
### BUGGY CODE ###

import heapq
n,m=map(int, input().split())
a=[list(map(int, input().split())) for i in range(n)]
a.sort(key=lambda x: x[1],reverse=True)
x=[1 for i in range(m)]
ans=0
count=0
q=[]

for i in range(1,m+1):
    for j in range(n):
        if a[j][0]==i: 
            heapq.heappush(q,-a[j][1])
    
    if len(q)!=0:
        ans+=-heapq.heappop(q)
        
            

print(ans)

        


        
        
    
    
        



### FIXED CODE ###

import heapq
def heapify(x):
    for i in reversed(range(n//2)):
        _siftup(x, i)
 
n,m = map(int,input().split())
 
l = []
for i in range(n):
    ab = list(map(int,input().split()))
    l.append(ab)
l.sort()
q = []
ans = 0
cnt = 0
for i in range(1,m+1):
    while cnt < n and l[cnt][0] == i:
        heapq.heappush(q,-l[cnt][1])
        cnt += 1
    
    if len(q) != 0:
        ans += -heapq.heappop(q)
 
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
#入力

N,K,Q=map(int,input().split())
a=[int(input()) for i in range(Q)]

for i in range(1,N+1,1):
    l=a.count(i)
    if(K+l-Q>0):print("Yes")
    else:print("No")


### FIXED CODE ###

# -*- coding: utf-8 -*-
#入力

N,K,Q=map(int,input().split())
a=[int(input()) for _ in range(Q)]
b=[0]*N
for i in a:
    b[i-1]+=1
for l in range(0,N,1):
    if(K+b[l]-Q>0):print("Yes")
    else:print("No")
### BUGGY CODE ###

import collections
n = int(input())
li = list(map(int,input().split()))
q = int(input())
num_li=[list(map(int,input().split())) for i in range(q)]

li.sort()
for i,j in num_li:
    if i in li:
        cnt = li.count(i)
        li = [k for k in li if k != i] + [j]*cnt
    print(sum(li))

### FIXED CODE ###

import collections
n = int(input())
li = list(map(int,input().split()))
q = int(input())
num_li=[list(map(int,input().split())) for i in range(q)]

c = collections.Counter(li)

li_sum = sum(li)

for i,j in num_li:
    s = 0
    if i in c:
        cnt = c.pop(i)
        c[j] += cnt
        li_sum = li_sum - (i*cnt) + (j*cnt)
    print(li_sum)
### BUGGY CODE ###

d, g = map(int, input().split())
pc = []
for _ in range(d):
    _p, _c = map(int, input().split())
    pc.append([_p, _c])
p = sum([i[0] for i in pc])
score = []
for i in range(len(pc)):
    for j in range(pc[i][0]):
        score.append((i+1)*100)
answer = 10000
for i in range(2 ** p):
    tmp = []
    ans = 0
    for j in range(p):
        if ((i >> j) & 1):
            tmp.append(j)
    for j in tmp:
        ans += score[j]
    for j in range(len(pc)):
        if j == 0:
            l = [_ for _ in tmp if 0 <= _ < pc[0][0]]
            if len(l) == pc[0][0]:
                ans += pc[0][1]
        elif j == len(pc)-1:
            s = score.index((j+1)*100)
            l = [_ for _ in tmp if s <= _]
            if len(l) == pc[-1][0]:
                ans += pc[-1][1]
        else:
            s = score.index((j+1)*100)
            e = score.index((j+1)*100) - 1
            l = [_ for _ in tmp if s <= _ <= e]
            if len(l) == pc[j][0]:
                ans += pc[j][1]
    if ans >= g:
        if answer > len(tmp):
            answer = len(tmp)
print(answer)

### FIXED CODE ###

d, g = map(int, input().split())
pc = []
a = 9999999
for _ in range(d):
    _p, _c = map(int, input().split())
    pc.append([_p, _c])
for i in range(2 ** d):
    tmp = []
    ans = 0
    n = 0
    for j in range(d):
        if ((i >> j) & 1):
            tmp.append(j)
    for j in tmp:
        ans += (j+1)*100*pc[j][0] + pc[j][1]
        n += pc[j][0]
    if ans >= g:
        if n < a:
            a = n
    else:
        for j in range(len(pc)):
            if not j in tmp:
                plus = 0
                for k in range(pc[j][0]):
                    plus += (j+1)*100
                    if ans + plus >= g:
                        if n + k + 1 < a:
                            ans += plus
                            n += k+1
                            a = n
                            break
print(a)
### BUGGY CODE ###

import bisect

A, B, Q = map(int, input().split())
Shrine = [int(input()) for _ in range(A)]
Temple = [int(input()) for _ in range(B)]

Shrine = [-100000000000] + Shrine + [100000000000]
Temple = [-100000000000] + Temple + [100000000000]

for i in range(Q):
    x = int(input())
    nums = bisect.bisect_left(Shrine, x)
    tems = bisect.bisect_left(Temple, x)
    ans1 = max(abs(Shrine[nums]-x), abs(Temple[tems]-x))
    ans2 = max(abs(x - Shrine[nums-1]), abs(x - Temple[tems-1]))
    ans3 = abs(Shrine[nums]-x) * 2 + abs(x - Temple[tems-1])
    ans4 = abs(Temple[tems]-x) * 2 + abs(x - Shrine[nums-1])
    ans5 = abs(x - Shrine[nums-1]) * 2 + abs(Temple[tems]-x)
    ans6 = abs(x - Temple[tems-1]) * 2 + abs(Shrine[nums]-x)

    print(min(ans1, ans2, ans3, ans4, ans5, ans6))

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline

A, B, Q = map(int, input().split())
Shrine = [int(input()) for _ in range(A)]
Temple = [int(input()) for _ in range(B)]
X = [int(input()) for _ in range(Q)]
Shrine = [-100000000000] + Shrine + [100000000000]
Temple = [-100000000000] + Temple + [100000000000]

for x in X:
    nums = bisect.bisect_left(Shrine, x)
    tems = bisect.bisect_left(Temple, x)
    ans1 = max(abs(Shrine[nums]-x), abs(Temple[tems]-x))
    ans2 = max(abs(x - Shrine[nums-1]), abs(x - Temple[tems-1]))
    ans3 = abs(Shrine[nums]-x) * 2 + abs(x - Temple[tems-1])
    ans4 = abs(Temple[tems]-x) * 2 + abs(x - Shrine[nums-1])
    ans5 = abs(x - Shrine[nums-1]) * 2 + abs(Temple[tems]-x)
    ans6 = abs(x - Temple[tems-1]) * 2 + abs(Shrine[nums]-x)

    print(min(ans1, ans2, ans3, ans4, ans5, ans6))
### BUGGY CODE ###

#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []
    for _ in range(n):
        v, w = LI()
        V.append(v)
        W.append(w)
    
    
    m = min(n, 1 << 10)
    dp = [[0]*(10**5 + 1) for _ in range(m + 1)]
    
    for i in range(1, m+1):
        v, w = V[i-1], W[i-1]
        for j in range(10**5 + 1):
            if j < w:
                dp[i][j] = dp[i>>1][j]
            else:
                dp[i][j] = max(dp[i>>1][j], dp[i>>1][j - w] + v)
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        tmp = v
        v_ = []
        w_ = []
        while tmp > m:
            v_.append(V[tmp-1])
            w_.append(W[tmp-1])
            tmp >>= 1
            cnt += 1
        ret = dp[tmp][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_tmp[b] = w_tmp[b - lsb] + w_[l-1]
            if w_tmp[b] <= L:
                v_tmp[b] = v_tmp[b - lsb] + v_[l-1]
                ret = max(ret, v_tmp[b] + dp[tmp][L - w_tmp[b]])
        print(ret)
    return

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []

    maxL = 10**5
    m = min(n, 1 << 10)
    dp = [[0]*(maxL + 1)]
    
    for i in range(n):
        v, w = LI()
        if i <= m:
            d_ = dp[(i+1)>>1][:]
            for j in range(w, maxL+1)[::-1]:
                d_[j] = max(d_[j], d_[j - w] + v)
            dp.append(d_)
        V.append(v)
        W.append(w)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        v_ = []
        w_ = []
        while v > m:
            v_.append(V[v-1])
            w_.append(W[v-1])
            v >>= 1
            cnt += 1
        ret = dp[v][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_t = w_tmp[b - lsb] + w_[l-1]
            w_tmp[b] = w_t
            if w_t <= L:
                v_t = v_tmp[b - lsb] + v_[l-1]
                v_tmp[b] = v_t
                ret = max(ret, v_t + dp[v][L - w_t])
        print(ret)
    return

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

n, k = map(int, input().split())
h = list(map(int, input().split()))
#高さ。0~n-1でアクセス

#足場Nにたどり着くまでの最小コストを格納。アクセスは[N-1]
dp = [float("inf")] * n

dp[0] = 0
dp[1] = abs(h[0] - h[1])

import sys
sys.setrecursionlimit(10000000)
#足場x（0～n-1）にたどり着くまでの最小コストを返す関数。
def getdp(x):
    global dp
    if dp[x] != float("inf"): return dp[x] #0の場合と、既に求めた場合は値を返す

    #今度はここをfor文にする
    #飛ぶ距離は、1～ min（ジャンプ力, xと0の距離(=x))
    mindp = float("inf") #最小値を初期化
    for i in range(1, min(k, x)+1, 1): #iはジャンプする距離(1~min(k,x))
        nowdp = getdp(x-i) + abs(h[x]-h[x-i])
        mindp = min(mindp, nowdp)
        dp[x] = mindp
    return(dp[x])

print(getdp(n-1))


### FIXED CODE ###

def solve():
  n,k=[int(i) for i in input().split()]
  h=[int(i) for i in input().split()]
  dp=[0]*n
  for i, hi in enumerate(h):
    if i==0: continue
    dp[i]=min([dp[j] + abs(hi-h[j]) for j in range(max(i-k,0),i)])
  return dp[n-1]
print(solve())
### BUGGY CODE ###

A,B = list(map(int,input().split()))
for i in range(2,A*B+1):
    if i % A == 0 and i % B == 0:
        print(i)
        break


### FIXED CODE ###

import fractions
A,B = list(map(int,input().split()))
print(int(A*B/fractions.gcd(A,B)))
### BUGGY CODE ###

from itertools import product

N = int(input())
XYP = [tuple(map(int, input().split())) for _ in range(N)]
X = [x for x, _, _ in XYP]
Y = [y for _, y, _ in XYP]
P = [p for _, _, p in XYP]
INF = 10**18

def calcCost(AP, A):
    ret = [[INF] * N for _ in range(1 << N)]
    for state in range(1 << N):
        useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
        for i, (a, p) in enumerate(AP):
            cost = abs(a)
            for z in useA:
                cost = min(cost, abs(a - z))
            ret[state][i] = cost * p
    return ret

costX = calcCost([(x, p) for x, _, p in XYP], X)
costY = calcCost([(y, p) for _, y, p in XYP], Y)

ans = [INF] * (N + 1)
for state in product((0, 1, 2), repeat=N):
    stateX = 0
    stateY = 0
    M = N
    for s in state:
        stateX <<= 1
        stateY <<= 1
        if s == 0: M -= 1
        if s == 1: stateX |= 1
        if s == 2: stateY |= 1

    cx, cy = costX[stateX], costY[stateY]
    cost = 0
    for s in map(min, zip(cx, cy)):
        cost += s
        if cost >= ans[M]:
            break
    else:
        ans[M] = cost

print(*ans, sep='\n')


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from numba import njit
import numpy as np
INF = 10**18

@njit('(i8, i8[:,:])')
def solve(N, XYP):
    X = XYP[:, 0]
    Y = XYP[:, 1]

    def calcCost(sign, A):
        ret = np.ones((1 << N, N), dtype=np.int64) * INF
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i in range(N):
                xyp = XYP[i]
                cost = abs(xyp[sign])
                for z in useA:
                    cost = min(cost, abs(xyp[sign] - z))
                ret[state][i] = cost * xyp[2]
        return ret

    costX = calcCost(0, X)
    costY = calcCost(1, Y)
    ans = np.ones(N + 1, dtype=np.int64) * INF

    for state in range(pow(3, N)):
        stateX = 0
        stateY = 0
        M = N
        for _ in range(N):
            state, r = divmod(state, 3)
            stateX <<= 1
            stateY <<= 1
            if r == 0: M -= 1
            if r == 1: stateX |= 1
            if r == 2: stateY |= 1

        cx, cy = costX[stateX], costY[stateY]
        cost = 0
        for i in range(N):
            cost += min(cx[i], cy[i])
        ans[M] = min(ans[M], cost)

    for a in ans:
        print(a)

def sol():
    N = int(input())
    XYP = np.asarray([list(map(int, input().split())) for _ in range(N)])
    solve(N, XYP)

sol()
### BUGGY CODE ###

def chmin(a, b):
    if a > b:
        return b
    else:
        return a
import numpy as np  
n,k = map(int,input().split())
h = np.array([int(i) for i in input().split()],dtype = np.int32)
# dpの最小値を変更する関数

# 無限大の値
f_inf = 10 ** 9 
# DP テーブルを初期化　(最小化問題なので INF に初期化)
dp = np.array([f_inf] * (10**5+10), dtype =np.int32)
# 初期条件
dp[0] = 0
# 足場 i-1 から足場 i へ移動する。コストは|h[i]−h[i-1]|
# 足場 i-2 から足場 i へと移動する コストは |h[i]−h[i-2]|
for i in range(1, n):
    for j in range(1,k+1):
        if i-j < 0 :
            continue
        else:
            dp[i] = chmin(dp[i], dp[i - j] + abs(h[i] - h[i-j]))
print(dp[n-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
def chmin(a, b):
    if a > b:
        return b
    else:
        return a
  
n,k = map(int,input().split())
h = [int(i) for i in input().split()]
# dpの最小値を変更する関数

# 無限大の値
f_inf = 10 ** 9 
# DP テーブルを初期化　(最小化問題なので INF に初期化)
dp = [f_inf] * (10**5+10)
# 初期条件
dp[0] = 0
# 足場 i-1 から足場 i へ移動する。コストは|h[i]−h[i-1]|
# 足場 i-2 から足場 i へと移動する コストは |h[i]−h[i-2]|
for i in range(1, n):
    for j in range(1,k+1):
        if i-j < 0 :
            continue
        else:
            dp[i] = chmin(dp[i], dp[i - j] + abs(h[i] - h[i-j]))
print(dp[n-1])
### BUGGY CODE ###

N = int(input())
Xn = list(map(int,input().split()))
import numpy as np

for i in range(N):
    Xn_numpy = np.array(Xn)
    Xn_deleted = np.delete(Xn_numpy, i)
    Xn_sort = np.sort(Xn_deleted)[::-1]
    a = (len(Xn_sort)+1)//2-1
    print(Xn_sort[a])

### FIXED CODE ###

n = int(input())
xm = list(map(int, input().split()))
xm_sort = sorted(xm)
a = n//2-1
for i in range(n):
    if xm[i]<=xm_sort[a]:
        print(xm_sort[a+1])
    else:
        print(xm_sort[a])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, a: "List[int]"):

    c = [0]*4
    for A in a:
        c[A] += 1

    J = min(c[2]+c[3]+1, N+1)
    I = min(c[1]+c[2]+c[3]+1, N+1)
    kitai = [[[0]*(I+1) for _ in range(J+1)]
             for _ in range(c[3]+1)]
    for k in range(c[3]+1):
        for j in range(J):
            for i in range(I):
                tot = i+j+k
                if tot == 0:
                    continue
                res = N + kitai[k][j][i-1]*i + \
                    kitai[k][j-1][i+1]*j + kitai[k-1][j+1][i]*k
                kitai[k][j][i] = res/tot
    print(kitai[c[3]][c[2]][c[1]])

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, a: "List[int]"):

    c = [0]*4
    for A in a:
        c[A] += 1

    J = min(c[2]+c[3]+1, N+1)
    I = min(c[1]+c[2]+c[3]+1, N+1)
    kitai = [[[0]*(I+1) for _ in range(J+1)]
             for _ in range(c[3]+1)]
    for k in range(c[3]+1):
        for j in range(J):
            for i in range(I):
                tot = i+j+k
                if tot == 0 or tot > N:
                    continue
                res = N + kitai[k][j][i-1]*i + \
                    kitai[k][j-1][i+1]*j + kitai[k-1][j+1][i]*k
                kitai[k][j][i] = res/tot
    print(kitai[c[3]][c[2]][c[1]])

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


if __name__ == '__main__':
    main()