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

# 動的計画法

n=int(input())
s=input()
dp=[[[False for k in range(1000)] for j in range(4)] for i in range(n+1)]

dp[0][0][0]=True

for i in range(n):
    for j in range(4):
        for k in range(1000):
            if dp[i][j][k]==False:continue
            dp[i+1][j][k]=True
            if j<=2:
                dp[i+1][j+1][k*10+int(s[i])]=True
cnt=0
for i in range(1000):
    if dp[n][3][i]==True:cnt+=1
print(cnt)

### FIXED CODE ###

n=int(input())
s=list(map(int,list(input())))
ans=0
for i in range(10):
    try:
        ss=s[s.index(i)+1:]
        for j in range(10):
            try:
                sss=ss[ss.index(j)+1:]
                for k in range(10):
                    if k in sss:ans+=1
            except:pass
    except:pass

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

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

b_list = []

for i, a in enumerate(a_list):
    if i % 2 == 0:
        b_list.insert(0, a)
    else:
        b_list.append(a)

if n % 2 ==0:
    b_list.reverse()
print(" ".join(map(str, b_list)))


### FIXED CODE ###

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

b_list_even = []
b_list_odd = []
for i, a in enumerate(a_list , start=1):
    if i % 2 == 0:
        b_list_even.append(a)
    else:
        b_list_odd.append(a)


if n % 2 != 0:
    b_list_odd.reverse()
    b_list = b_list_odd + b_list_even
else:
    b_list_even.reverse()
    b_list = b_list_even + b_list_odd

print(" ".join(map(str, b_list)))
### BUGGY CODE ###

import itertools
N = int(input())
S = list(input())
s = set(itertools.combinations(S, 3))
print(len(s))

### FIXED CODE ###

import itertools
N = int(input())
S = list(input())
S = list(map(int, S))
first = [-1] * 10
#second = [-1] * 10
#third = [-1] * 10
ans = 0
for i in range(N):
    if first[S[i]] == 1:
        continue
    second = [-1] * 10
    for j in range(i + 1, N):
        if second[S[j]] == 1:
            continue
        third = [-1] * 10
        for k in range(j + 1, N):
            if third[S[k]] == 1:
                continue
            #print(S[i], S[j], S[k])
            ans += 1
            third[S[k]] = 1
        second[S[j]] = 1
    first[S[i]] = 1
print(ans)
### BUGGY CODE ###

import numpy as np
import sys
import bisect

readline = sys.stdin.readline

# 入力にかかる最大計算量O(NlogN)：クイックソート
N = int(input())
A = np.array(readline().split(), np.int64)
A_sort = np.sort(A)
Q = int(input())
BC = np.array([np.array(readline().split(), np.int64) for n in range(Q)], np.int64)
# BC[N][0,1]

# ここの計算量O(N(logN + logN))
for q in range(Q):
    # A = [BC[q][1] if x==BC[q][0] else x for x in A]
    A[bisect.bisect_left(A, BC[q][0]):bisect.bisect_right(A, BC[q][0])] = BC[q][1]
    print(sum(A))



### FIXED CODE ###

import numpy as np
import sys
from bisect import bisect_right, bisect_left

readline = sys.stdin.readline

# 入力にかかる最大計算量O(NlogN)：クイックソート
N = int(input())
A = np.array(readline().split(), np.int64)
num_array = np.zeros(10**5, np.int64)
for n in A:
    num_array[n-1] += 1

# A_sort = np.sort(A)
A_sum = sum(A)
Q = int(input())
BC = np.array([np.array(readline().split(), np.int64) for n in range(Q)], np.int64)
# BC[N][0,1]

# ここの計算量O(N(logN + logN))
for q in range(Q):
    # A = [BC[q][1] if x==BC[q][0] else x for x in A]
    # A[bisect.bisect_left(A, BC[q][0]):bisect.bisect_right(A, BC[q][0])] = BC[q][1]
    '''
    plus_num = BC[q][1] - BC[q][0]
    left = bisect_left(A_sort, BC[q][0])
    right = bisect_right(A_sort, BC[q][0])
    plus_multiple = right - left
    A_sort[left:right] = BC[q][1]
    A_sort = np.sort(A_sort)
    '''

    '''
    plus_num = BC[q][1] - BC[q][0]
    plus_multiple = np.count_nonzero(A == BC[q][0])
    A[A==BC[q][0]] = BC[q][1]
    '''

    plus_num = BC[q][1] - BC[q][0]
    plus_multiple = num_array[BC[q][0] - 1]
    # リスト内の要素数の更新
    num_array[BC[q][1]- 1] += num_array[BC[q][0] - 1]
    num_array[BC[q][0] - 1] = 0

    A_sum = A_sum + plus_num*plus_multiple
    print(A_sum)
### BUGGY CODE ###

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

def primeFactorization2(x):
    ps = []
    es = []
    i=2
    while i<=x:
        if x%i==0 and isPrime(i):
            ps.append(i)
            e=0
            while x%i==0:
                x = x//i
                e+=1
            es.append(e)
        i+=1
    return [ps, es]


n=int(input())
nums = primeFactorization2(n)[1]

ans=0
for i in nums:
    ans += int(((1+8*i)**0.5-1)/2)

if isPrime(n):
    print(1)
else:
    print(ans)
    
            
        
    
    
    


### FIXED CODE ###

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

def primeFactorization2(x):
    ps = []
    es = []
    i=2
    k=x
    while i<=k**0.5:
        if k%i==0 and isPrime(i):
            ps.append(i)
            e=0
            while k%i==0:
                k = k//i
                e+=1
            es.append(e)
        i+=1
    if x==1:
        return [[],[]]
    elif isPrime(x):
        return [[x],[1]]
    else:
        return [ps + primeFactorization2(k)[0], es + primeFactorization2(k)[1]]


n=int(input())

if isPrime(n):
    print(1)
else:
    nums = primeFactorization2(n)[1]

    ans=0
    for i in nums:
        ans += int(((1+8*i)**0.5-1)/2)

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

# from math import factorial,sqrt
# from itertools import permutations as permus
# from fractions import gcd
from collections import deque,Counter
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
# import scipy as scp

# 入力の受け取り
n = int(input())
arrA = list(map(int,input().split()))

ctA = Counter(arrA)
ans = []
for i in arrA:
    ctA[i] -= 1
    temp = 0
    for k,v in ctA.items():
        if v>1:
            temp += v*(v-1)//2
    print(temp)
    ctA[i] += 1

# print(*ans,sep="\n")
# print("{:.10f}".format(ans))
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する



### FIXED CODE ###

# from math import factorial,sqrt
# from itertools import permutations as permus
# from fractions import gcd
from collections import deque,Counter
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
# import scipy as scp

# 入力の受け取り
n = int(input())
arrA = list(map(int,input().split()))

cbdp = [0,0]
cbdp2 = [i*(i-1)//2 for i in range(2,n+1)]
cbdp += cbdp2
# print(cbdp)

ctA = Counter(arrA)
# print(ctA)

totalconb = 0
for v in ctA.values():
    totalconb += cbdp[v]
# print(totalconb)

for a in arrA:
    print(totalconb-cbdp[ctA[a]]+cbdp[ctA[a]-1])

# print(*ans,sep="\n")
# print("{:.10f}".format(ans))
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
### BUGGY CODE ###



import sys
import math
from bisect import bisect_right
def main():
    N,M = map(int,input().split())
    Marray=[(0,0)] * M
    P={}
    for i in range(M):
        s = input().split()
        p=int(s[0])
        y=s[1]
        #print(s)
        if p in P.keys():
            P[p]+=y+","
        else:
            P[p]=y+","
        Marray[i]=(p,int(y))
        #print(P[p])
        
    for key in P:
        string=P[key]
        
       # print(str)
        sp=string.split(",")
        de=len(sp)-1
        del sp[de]
        #print(sp)
        tmp=sorted(sp,key=int)
        P[key]=tmp
        
        #print(P[key])
    
    for index,value in Marray:
        list=P[index]
        list = [int(s) for s in list]
        #print(list)
        result=bisect_right(list,value)
        result=str(result)
        index=str(index)
        index_zero = index.zfill(6)
        result_zero = result.zfill(6)
        print(index_zero,result_zero,sep='')









if __name__ == "__main__":
    main()







### FIXED CODE ###

import sys
import math
from bisect import bisect_right
def main():
    N,M = map(int,input().split())
    Marray=[(0,0)] * M
    P={}
    for i in range(M):
        s = input().split()
        p=int(s[0])
        y=s[1]
        #print(s)
        if p in P.keys():
            P[p].append(int(y))
        else:
            P[p]=[]
            P[p].append(int(y))
        Marray[i]=(p,int(y))
        #print(P[p])
        
    for key in P:
        #string=P[key]
        
       # print(str)
        #sp=string.split(",")
        #de=len(sp)-1
        #del sp[de]
        #print(sp)
        tmp=sorted(P[key],key=int)
        #int_list=list(map(int,tmp))
        P[key]=tmp
        
        #print(P[key])
    
    for index,value in Marray:
        List=P[index]
        
        #print(list)
        result=bisect_right(List,value)
        result=str(result)
        index=str(index)
        index_zero = index.zfill(6)
        result_zero = result.zfill(6)
        print(index_zero,result_zero,sep='')



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

import sys
input=sys.stdin.readline
n,k=map(int,input().split())
lists=list(map(int,input().split()))
GG=[]
for i in range(len(lists)+1):
    for j in range(i,len(lists)):
        
        G=sum(lists[i:j+1])
        GG.append(G)
        
GG=sorted(GG,reverse=True)      
maxi=format(GG[0],"b")
from collections import deque
d=deque()
e=deque()
for j in range(len(GG)):
    d.append(format(GG[j],"b").zfill(len(maxi)))
answer=0
index=0

while index!=len(maxi):
    counter=0
    for some in d:
        if some[index]=="1":
            counter+=1
            e.append(some)
    if counter>=k:
        answer+=2**(len(maxi)-1-index)
        d=e
        e=deque()
    elif counter<k:
        d=d
        e=deque()
        
    index+=1
    counter=0


print(answer)


### FIXED CODE ###

n,k=map(int,input().split())
lists=list(map(int,input().split()))
GG=[]
sumlist=[0]
a=0
for i in range(len(lists)):
    a+=lists[i]
    sumlist.append(a) 
for i in range(len(sumlist)):
    for j in range(i+1,len(sumlist)):
        
        G=sumlist[j]-sumlist[i]
        GG.append(G)
        
GG=sorted(GG,reverse=True)      
maxi=format(GG[0],"b")
from collections import deque
d=deque()
e=deque()
for j in range(len(GG)):
    d.append(format(GG[j],"b").zfill(len(maxi)))
answer=0
index=0
 
while index!=len(maxi):
    counter=0
    for some in d:
        if some[index]=="1":
            counter+=1
            e.append(some)
    if counter>=k:
        answer+=2**(len(maxi)-1-index)
        d=e
        e=deque()
    elif counter<k:
        d=d
        e=deque()
        
    index+=1
    counter=0
print(answer)
### BUGGY CODE ###

N = int(input())
ans = 0
for i in range(N):
    ans += i

print(ans)

### FIXED CODE ###

N = int(input())
 
    
ans = (N  * (N - 1))
ans = ans // 2

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

import bisect

N = int(input())
now_top = -1
color = 1
prev_tops = []
for n in range(N):
    x = int(input())
    if x > now_top:
        now_top = x
    else:
        b = bisect.bisect_left(prev_tops, x)
        if b == 0:
            prev_tops.append(now_top)
            color += 1
            now_top = x
        else:
            b = b - 1
            push = now_top
            now_top = prev_tops[b]
            prev_tops = prev_tops[:b] + prev_tops[b+1:]
            prev_tops.append(push)
        prev_tops.sort()
print(color)


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import bisect

def iterate_tokens():
    for line in sys.stdin:
        for word in line.split():
            yield word

def solve(N: int):
    tokens = iterate_tokens()
    colors_top = []
    for i in range(N):
        new = int(next(tokens))
        if colors_top:
            b = bisect.bisect_right(colors_top, -new)
            if b == len(colors_top):
                colors_top.append(-new)
            else:
                colors_top[b] = -new
        else:
            colors_top.append(-new)
    print(len(colors_top))
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

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

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

H = [0] * N
for i in range(N):
    H[i] = int(input())

H.sort()

d = max(H)
for i in range(N-K+1):
    d = min(max(H[i:i+K]) - min(H[i:i+K]), d)
print(d)

### FIXED CODE ###

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

H = [0] * N
for i in range(N):
    H[i] = int(input())
H.sort()

d = H[K-1] - H[0]
for i in range(1, N-K+1):
    d = min(H[i+K-1] - H[i], d)
print(d)
### BUGGY CODE ###

from collections import deque

def bfs(start):
    queue = deque([start])
    visited = []

    while queue:
        label = queue.pop()

        if label not in visited:
            visited.append(label)

            for v in d[label]:
                if v[0] not in visited:
                    dist[v[0]] = dist[label] + v[1]
                    queue.appendleft(v[0])

    return

n = int(input())
d = [[] for _ in range(n)]
for _ in range(n - 1):
	a, b, c = map(int, input().split())
	d[a - 1].append([b - 1, c])
	d[b - 1].append([a - 1, c])

q, k = map(int, input().split())
dist = [0 for _ in range(n)] # nは頂点数

bfs(k - 1)

for _ in range(q):
	x, y = map(int, input().split())
	print(dist[x - 1] + dist[y - 1])

### FIXED CODE ###

from collections import deque

def bfs(start):
    queue = deque([start])
    visited = []

    while queue:
        label = queue.pop()

        #if label not in visited:
        visited.append(label)

        for v in d[label]:
            if dist[v[0]] == float("inf"):
                dist[v[0]] = dist[label] + v[1]
                queue.appendleft(v[0])

    return

n = int(input())
d = [[] for _ in range(n)]
for _ in range(n - 1):
	a, b, c = map(int, input().split())
	d[a - 1].append([b - 1, c])
	d[b - 1].append([a - 1, c])

q, k = map(int, input().split())
dist = [float("inf") for _ in range(n)] # nは頂点数
dist[k - 1] = 0

bfs(k - 1)

for _ in range(q):
	x, y = map(int, input().split())
	print(dist[x - 1] + dist[y - 1])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
for i in a:
    ans *= i
if ans > 10**18:
    print('-1')
else:
    print(int(ans))

### FIXED CODE ###

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

if 0 in a:
    ans = 0
else:
    ans = 1
    for i in a:
        ans *= i
        if ans > 10**18:
            ans = -1
            break
print(ans)
### BUGGY CODE ###

from collections import deque

def bfs(idx,k):
  q = deque()
  visited[idx] = True
  q.append(idx)
  color = 0
  while q:
    r = q.pop()
    col = graph[r].values()
    for n in set(graph[r].keys()):
      if not visited[n]:
        if color not in set(col):
          graph[r][n] = color
          graph[n][r] = color
          color = (color+1)%k
        else:
          color = (color+1)%k
          graph[r][n] = color
          graph[n][r] = color
          color = (color+1)%k
        visited[n] = True
        q.append(n)

        
N = int(input())
graph = {}
visited = [False]*(N+1)
for i in range(N+1):
  graph[i] = {}
ab = []
for i in range(N-1):
  a,b = map(int,input().split())
  ab.append((a,b))
  graph[a][b] = -1
  graph[b][a] = -1
  
k = 0
for i in range(1,N+1):
  k = max(k,len(graph[i]))

bfs(1,k)
print(k)
for i in range(N-1):
  a,b = ab[i]
  print(graph[a][b]+1)

  


  


### FIXED CODE ###

from collections import deque

def bfs(idx,k,colored):
  q = deque()
  visited[idx] = True
  q.append(idx)
  while q:
    r = q.pop()
    color = 0
    for n in graph[r].keys():
      if not visited[n]:
        if color == colored[r]: color+=1
        colored[n] = color
        graph[r][n] = color
        graph[n][r] = color
        color += 1

        visited[n] = True
        q.append(n)

        
N = int(input())
graph = {}
colored = [-1]*(N+1)
visited = [False]*(N+1)
for i in range(N+1):
  graph[i] = {}
ab = []
for i in range(N-1):
  a,b = map(int,input().split())
  ab.append((a,b))
  graph[a][b] = -1
  graph[b][a] = -1
  
k = max([len(graph[i]) for i in range(1,N+1)])

bfs(1,k,colored)
print(k)
for a,b in ab:
  print(graph[a][b]+1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def main():
    N = int(input())
    A = ["?"]*N

    l, x, r = 0, N//2, N-1
    while True:
        ls = A[l]
        if ls == "?":
            print(l)
            ls = input().strip()
            A[l] = ls

        xs = A[x]
        if xs == "?":
            print(x)
            xs = input().strip()
            A[x] = xs

        rs = A[r]
        if rs == "?":
            print(r)
            rs = input().strip()
            A[r] = rs

        if ls != xs:
            l, x, r = l, (l+x)//2, x
        elif rs != xs:
            l, x, r = x, (x+r)//2, r


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


def q(i):
    print(i, flush=True)
    s = input().strip()
    if s == "Vacant":
        exit()
    return s


def f(l, r, lc, rc):
    m = (l+r)//2
    mc = q(m)

    if ((m-l) % 2 and lc == mc) or ((m-l) % 2 == 0 and lc != mc):
        f(l, m, lc, mc)
    elif ((r-m) % 2 and mc == rc) or ((r-m) % 2 == 0 and mc != rc):
        f(m, r, mc, rc)


def main():
    N = int(input())
    lc = q(0)
    rc = q(N-1)
    f(0, N-1, lc, rc)


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

N=int(input())
S=list(str(input()))
ans=0
for i in range(N):
  for j in range(i+1,N-1):
    if S[i] != S[j]:
      for k in range(j+1,N):
        if S[i]!=S[k] and S[j]!=S[k]:
          if j-i!=k-j:
            ans+=1
print(ans)

### FIXED CODE ###

N=int(input())
S=input()
a=S.count('R')
b=S.count('G')
c=S.count('B')
ans=a*b*c
for i in range(N-2):
  for j in range(i+1,N-1):
    if S[i]!=S[j]:
      if (2*j-i)<=N-1 and S[i]!=S[2*j-i]!=S[j]:
        ans-=1     
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
ab = {i:[] for i in range(m+1)}
for i in range(n):
    a,b = map(int,input().split())
    if a in ab:
        ab[a].append(b)
    else:
        ab[a] = [b]
#print(ab)
ans = 0
for i in range(m)[::-1]:
    rem = m - i
    if ab[rem]:
        job = ab[rem]
        ans += max(job)
        del ab[rem][job.index(max(job))]
        if rem < m:
            ab[rem+1] += ab[rem]
    #print(ans)
print(ans)


### FIXED CODE ###

from heapq import *
n,m = map(int,input().split())
t = [[] for i in range(10**5+1)]
for i in range(n):
    a,b = map(int,input().split())
    t[a].append(b)

ans = 0
h = []
for i in range(1,m+1):
    #print(i,"日目")
    for j in t[i]:
        heappush(h, -j)
        #print("heappush",j)
    if h:
        a = -heappop(h)
        #print("heappop",a)
        ans += a
print(ans)
### BUGGY CODE ###

N = int(input())
A = []
for _ in range(N):
  a = int(input())
  A.append(a)

check = [False for _ in range(N)]
cnt = 0
for i in range(N):
  if check[i] == False:
    cnt += 1
  for j in range(i + 1, N):
    if A[j] > A[i]:
      check[j] = True
      check[i] = True
print(cnt)

### FIXED CODE ###

import bisect
from collections import deque

N = int(input())
A = []
for _ in range(N):
  a = int(input())
  A.append(a)

b = deque([])
for a in A:
  if len(b) == 0:
    b.append(a)
  else:
    if a <= b[0]:
      b.appendleft(a)
    else:
      b[bisect.bisect_left(b, a) - 1] = a
print(len(b))
### BUGGY CODE ###

def comb(n, r):
    if r<0 or r>n:
        return 0
    r=min(r, n-r)
    return g1[n]*g2[r]*g2[n-r]%MOD

MOD=10**9+7
MAXN=10**6*2+10
g1=[1, 1]
g2=[1, 1]
inverse=[0, 1]

for i in range(2, MAXN+1):
    g1.append((g1[-1]*i)%MOD)
    inverse.append(-inverse[MOD%i]*(MOD//i)%MOD)
    g2.append((g2[-1]*inverse[-1])%MOD)

r1, c1, r2, c2=map(int, input().split())
s1=comb(r2+c2+2, r2+1)
s2=comb(r1+c2+1, r1)
s3=comb(r2+c1+1, r2+1)
s4=comb(r1+c1, r1)
print(s1-s2-s3+s4)


### FIXED CODE ###

def comb(n, r):
    if r<0 or r>n:
        return 0
    r=min(r, n-r)
    return g1[n]*g2[r]*g2[n-r]%MOD

MOD=10**9+7
MAXN=2000000+10
g1=[1, 1]
g2=[1, 1]
inverse=[0, 1]

for i in range(2, MAXN+1):
    g1.append((g1[-1]*i)%MOD)
    inverse.append(-inverse[MOD%i]*(MOD//i)%MOD)
    g2.append((g2[-1]*inverse[-1])%MOD)

r1, c1, r2, c2=map(int, input().split())
s1=comb(r2+c2+2, r2+1)-1
s2=comb(r1+c2+1, r1)-1
s3=comb(r2+c1+1, r2+1)-1
s4=comb(r1+c1, r1)-1
print((s1-s2-s3+s4)%MOD)
### BUGGY CODE ###

from fractions import gcd
 
N = int(input())
A = list(map(int, input().split()))
 
ans = 0
 
for i in range(N):
    tmp = A[:i] + A[i + 1:]
    g = 0
    for j in range(N - 1):
        g = gcd(tmp[j], g)
    ans = max(g, ans)
 
print(ans)

### FIXED CODE ###

from fractions import gcd
 
N = int(input())
A = list(map(int, input().split()))
l = []
r = []
k = 0
for i in range(N):
    k = gcd(k , A[i])
    l.append(k)
k = 0
for i in range(N - 1, -1, -1):
    k = gcd(k, A[i])
    r.append(k)
ans = 0
for i in range(N):
    ans = max(ans, gcd(l[i - 1], r[N - i - 2]))

ans = max(ans, l[N - 2], r[N - 2])

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

N,K=list(map(int, input().split()))
h=list(map(int, input().split()))
history=[0]*N
if N-1<=K:#無理久保なんですけど～～～
	print(abs(h[N-1]-h[0]))
else:#可能久保
	for made in range(1,K):#自明な履歴つくりまーっす
		kouho=[]
		for kara in range(0,made):
			kouho.append(history[kara]+abs(h[made]-h[kara]))
		history[made]=min(kouho)
	for made in range(K,N):#履歴踏まえのみ履歴を作りながら進む
		kouho=[]
		for kara in range(made-K,made):
			kouho.append(history[kara]+abs(h[made]-h[kara]))
		history[made]=min(kouho)
	print(history[N-1])
#print(history)

### FIXED CODE ###

N,K=list(map(int, input().split()))
h=list(map(int, input().split()))
history=[0]*N
if N-1<=K:#無理久保なんですけど～～～
	print(abs(h[N-1]-h[0]))
else:#可能久保
	for made in range(1,K):#自明な履歴つくりまーっす
		kouho=[]
		for kara in range(0,made):
			kouho.append(history[kara]+abs(h[made]-h[kara]))
		history[made]=min(kouho)
	for made in range(K,N):#履歴踏まえのみ履歴を作りながら進む
		kouho=[]
		for kara in range(made-K,made):
			kouho.append(history[kara]+abs(h[made]-h[kara]))
		history[made]=min(kouho)
	print(history[N-1])
#print(history)
### BUGGY CODE ###

N = int(input())
A = [int(x) for x in input().split()]
kosuu = [0]*(N+1)
num = []
for i in range(N):
    kosuu[A[i]] += 1
for i in range(N):
    if kosuu[A[i]] >= 2:
        num.append(i)

base = 0
for i in kosuu:
    base += i*(i-1)//2
for i in range(N):
    if i not in num:
        print(base)
    else:
        print(base - (kosuu[A[i]]-1))

### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
kosuu = [0]*(N+1)
for i in range(N):
    kosuu[A[i]] += 1

base = 0
for i in kosuu:
    base += i*(i-1)//2
for i in range(N):
    print(base-(kosuu[A[i]]-1))
### BUGGY CODE ###

import sys

def mink(numk,l):
    x = 1
    for _ in range(k):
        x = a[x-1]
    return x

input = sys.stdin.readline
n,k = map(int,input().split())
a = list(map(int,input().split()))

# kが小さい時
if k <= 10**16:
    print(mink(k,a))
    sys.exit()

z = 1
p = [1]
for _ in range(k):
    z = a[z-1]
    if z in p:
        p.append(z)
        break
    p.append(z)

# 周期の来る前の回数
num = p.index(p[-1])

p = p[num:]

# 周期
pn = len(p)-1

k -= num

# 回数/周期のあまり
anum = k%pn
print(p[anum])


### FIXED CODE ###

import sys

input = sys.stdin.readline
n,k = map(int,input().split())
a = list(map(int,input().split()))

p = [1]
for i in range(n):
    p.append(a[p[i]-1])

if k <= n:
    print(p[k])
else:
    # 周期の来る前の回数
    num = p.index(p[-1])
    p = p[num:]

    # 周期
    pn = len(p)-1
    k -= num

    # 回数/周期のあまり
    ans = k%pn
    print(p[ans])
### BUGGY CODE ###

import collections
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
N = int(input())
A = list(map(int,input().split()))
for i in range(N):
    ans = 0
    B = A[:i] + A[i+1:]
    C = collections.Counter(B)
    for j in set(B):
        D = C[j]
        if D > 1:
            ans += combinations_count(D,2)
    print(ans)

### FIXED CODE ###

import collections
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
N = int(input())
A = list(map(int,input().split()))
B = collections.Counter(A)
num = 0
for i in set(A):
    if B[i] > 1:
        num += combinations_count(B[i], 2)
for i in A:
    print(num-B[i]+1)