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

import sys

# import re
# import math
# import collections
# import decimal
# import bisect
# import itertools
# import fractions
# import functools
# import copy
# import heapq
# import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    edge = [[] for i in range(n)]
    origin_edge = []
    edge_dic = {}
    for i in range(n - 1):
        a, b = ns()
        a -= 1
        b -= 1
        edge[a].append(b)
        edge[b].append(a)
        edge_dic[(a, b)] = -1
        origin_edge.append((a, b))

    max_root = 0
    for e in edge:
        max_root = max(max_root, len(e))

    node_unused_color = [{i for i in range(max_root)} for j in range(n)]

    que = queue.Queue()
    que.put(0)

    while que.qsize() > 0:
        node = que.get()
        for k in edge[node]:
            ai = min(node, k)
            bi = max(node, k)

            if edge_dic[(ai, bi)] > -1:
                continue

            choices = node_unused_color[ai] & node_unused_color[bi]
            chosen_color = min(choices)
            node_unused_color[ai] -= {chosen_color}
            node_unused_color[bi] -= {chosen_color}
            edge_dic[(ai, bi)] = chosen_color
            que.put(k)

    print(max_root)
    for a, b in origin_edge:
        print(edge_dic[(a, b)]+1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

# import re
# import math
# import collections
# import decimal
# import bisect
# import itertools
# import fractions
# import functools
# import copy
# import heapq
# import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    edge = [[] for i in range(n)]
    origin_edge = []
    edge_dic = {}
    for i in range(n - 1):
        a, b = ns()
        a -= 1
        b -= 1
        edge[a].append(b)
        edge[b].append(a)
        edge_dic[(a, b)] = -1
        origin_edge.append((a, b))

    max_root = 0
    for e in edge:
        max_root = max(max_root, len(e))

    que = queue.Queue()
    que.put((0, -1))

    while que.qsize() > 0:
        node, used_color = que.get()
        current_color = 0 if used_color != 0 else 1
        for k in edge[node]:
            ai = min(node, k)
            bi = max(node, k)

            if edge_dic[(ai, bi)] > -1:
                continue

            edge_dic[(ai, bi)] = current_color
            que.put((k, current_color))
            current_color = current_color + 1 if used_color != current_color + 1 else current_color + 2

    print(max_root)
    for a, b in origin_edge:
        print(edge_dic[(a, b)] + 1)


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

N,K=map(int,input().split())
A=list(map(int,input().split()))
nA=[a for a in A if a<0]
pA=[a for a in A if a>=0]
nA.sort(reverse=True)
pA.sort()

#積がx以下になる組み合わせの数
def f(x):
    ret=0
    for na in nA:
        ret+=g1(nA,na,x)-(1 if na*na<=x else 0)
        ret+=g2(pA,na,x)
    for pa in pA:
        ret+=g2(nA,pa,x)
        ret+=g1(pA,pa,x)-(1 if pa*pa<=x else 0)
    return ret//2

#単調増加の場合の組み合わせ数
def g1(L,n,x):
    if len(L)==0: return 0
    if L[0]*n>x: return 0
    l=0
    over=len(L)
    while over-l>1:
        m=(over+l)//2
        if L[m]*n<=x: l=m
        else: over=m
    return l+1

#単調減少の場合の組み合わせ数
def g2(L,n,x):
    if len(L)==0: return 0
    if L[-1]*n>x: return 0
    under=-1
    r=len(L)-1
    while r-under>1:
        m=(under+r)//2
        if L[m]*n<=x: r=m
        else: under=m
    return len(L)-r

#組み合わせがK個未満になる最大のxを求める(l)
l=-10**19
r=10**19
while r-l>1:
    m=(r+l)//2
    if f(m)<K: l=m
    else: r=m
print(r)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N,K=map(int,input().split())
A=list(map(int,input().split()))
nA=[a for a in A if a<0]
zero=[a for a in A if a==0]
pA=[a for a in A if a>0]
nA.sort(reverse=True)
pA.sort()

pR=0
neg=len(nA)*len(pA)*2
zzz=len(zero)*(N-len(zero)+N-1)

#積がx以下になる組み合わせの数
def f(x):
    global pR
    ret=0
    if x<0:
        pR=len(pA)-1
        for na in nA:
            while pR>=0:
                if na*pA[pR]>x: break
                pR-=1
            ret+=len(pA)-pR-1
    elif x==0:
        ret+=neg
        ret+=zzz
        ret//=2
    else:
        ret+=neg
        ret+=zzz
        pR=len(nA)-1
        for na in nA:
            while pR>=0:
                if na*nA[pR]<=x: break
                pR-=1
            ret+=pR+1
            ret-=1 if na*na<=x else 0
        pR=len(pA)-1
        for pa in pA:
            while pR>=0:
                if pa*pA[pR]<=x: break
                pR-=1
            ret+=pR+1
            ret-=1 if pa*pa<=x else 0
        ret//=2
    return ret
#組み合わせがK個未満になる最大のxを求める(l)
l=-10**18-1
r=10**18
while r-l>1:
    m=(r+l)//2
    if f(m)<K: l=m
    else: r=m
print(r)
### BUGGY CODE ###

N = int(input())
As = list(map(lambda x: int(x), input().split(" ")))

result = 0
MOD = 10**9+7

for i in range(len(As)-1):
    for j in range(i+1, len(As)):
        tmp = As[i] * As[j]
        tmp %= MOD
        result = (result+tmp) % MOD

print(result)


### FIXED CODE ###

N = int(input())
As = list(map(lambda x: int(x), input().split(" ")))

result = 0
MOD = 10**9+7

S = sum(As)

for i in range(len(As)-1):
    S -= As[i]
    tmp = As[i] * S
    result += tmp
    result %= MOD

print(result)
### BUGGY CODE ###

from heapq import heappop, heappush, heapify
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
heap = list(map(int, input().split()))
heapify(heap)

for _ in range(M):
    B, C = map(int, input().split())
    for _ in range(B):
        tmp = heappop(heap)
        if tmp < C:
            heappush(heap, C)
        else:
            heappush(heap, tmp)
print(sum(heap))

### FIXED CODE ###

from heapq import heappop, heappush, heapify
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
heap = list(map(int, input().split()))
heapify(heap)

BC = []
for _ in range(M):
    B, C = map(int, input().split())
    BC.append([B, C])
BC.sort(key=lambda x: -x[1])

for B, C in BC:
    for _ in range(B):
        tmp = heappop(heap)
        if tmp < C:
            heappush(heap, C)
        else:
            heappush(heap, tmp)
            break
print(sum(heap))
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline

    s = input()[:-1]
    q = int(input())

    for _ in range(q):
        query = input()
        if query[0] == '1':
            s = s[::-1]
        else:
            if query[2] == '1':
                s = query[4] + s
            else:
                s += query[4]

    print(s)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    s = input()
    q = int(input())

    rule = 0
    pre, suf = '', ''
    for _ in range(q):
        query = input()
        if query[0] == '1':
            rule += 1
        else:
            if rule % 2 == 0:
                if query[2] == '1':
                    pre = query[4] + pre
                else:
                    suf += query[4]
            else:
                if query[2] == '1':
                    suf += query[4]
                else:
                    pre = query[4] + pre

    s = pre + s + suf
    print(s if rule % 2 == 0 else s[::-1])


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

n = input()

S = map(int, raw_input().split())

q = input()

T = map(int, raw_input().split())

S.append(0)
cnt = 0
for i in range(q):
    j = 0
    S[n] = T[i]
    while S[j] != S[n]:
        j = j + 1
    if j != n:
        cnt = cnt + 1


print cnt

### FIXED CODE ###

n = input()

S = map(int, raw_input().split())

q = input()

T = map(int, raw_input().split())

cnt = 0
for j in range(q):
    left = 0
    right = n
    while left < right:
        mid = (left + right) / 2
        if S[mid] == T[j]:
            cnt = cnt + 1
            break
        elif T[j] < S[mid]:
            right = mid
        else:
            left = mid + 1

print cnt
### BUGGY CODE ###

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

# スペース区切りの整数の入力
h, w, m = map(int, input().split())

h_list = [0]*h
w_list = [0]*w


h_w_list = [[0 for j in range(w)] for i in range(h)]

for zzz in range(m):
  # print("---")
  bom_h, bom_w = map(int, input().split())
  # print(bom_h, bom_w)
  h_list[bom_h-1] = h_list[bom_h-1] + 1
  w_list[bom_w-1] = w_list[bom_w-1] + 1

  h_w_list[bom_h-1][bom_w-1] = "target"

h_max_indexs = [i for i, v in enumerate(h_list) if v == max(h_list)]
# print(h_max_indexs)

w_max_indexs = [i for i, v in enumerate(w_list) if v == max(w_list)]
# print(w_max_indexs)


double_chance = False
# print("---")
for h_index in h_max_indexs:
  if double_chance:
    break
  for w_index in w_max_indexs:
    if double_chance:
      break
    chance = h_w_list[h_index][w_index] != "target"

    # print(h_index, w_index, chance)
    if chance:
      double_chance = True


if double_chance:
  result = h_list[h_index] + w_list[w_index]
else:
  result = h_list[h_index] + w_list[w_index] -1

print(result)


### FIXED CODE ###

H,W,M = map(int,input().split())
listh = [0] * H
listw = [0] * W
s = set()
for i in range(M):
    hm,wm = map(int,input().split())
    listh[hm-1] += 1
    listw[wm-1] += 1
    s.add((hm-1,wm-1))
mh = max(listh)
mw = max(listw)
maxh = [i for i,v in enumerate(listh) if v == mh]
maxw = [i for i,v in enumerate(listw) if v == mw]

import sys
for i in maxh:
    for j in maxw:
        if (i,j) not in s:
            print(mh + mw)
            sys.exit()
print(mh + mw - 1)
### BUGGY CODE ###

def extractMax(A):
    x = A[0]
    A[0] = A[-1]
    A.pop()
    H = len(A)
    i = 0
    while i < H:
        r = (i+1) * 2
        l = r - 1
        if l < H:
            lv = A[l]
        else:
            lv = 0
        if r < H:
            rv = A[r]
        else:
            rv = 0
        if lv == 0 and rv == 0:
            break
        elif A[i] < lv and lv > rv:
            A[l] = A[i]
            A[i] = lv
            i = l
        elif A[i] < rv:
            A[r] = A[i]
            A[i] = rv
            i = r
        else:
            break
    return x

def insert(A,n):
    A.append(n)
    i = len(A) - 1
    while i > 0:
        p = int((i + 1) / 2) - 1
        if A[p] < A[i]: # ???????????§??????
            x = A[p]
            A[p] = A[i]
            A[i] = x
            i = p
        else:
            break

def main():

    """ ????????? """
    end = False
    S = []
    
    while end != True:
        cmd = input()
#        print("cmd:{} S:{}".format(cmd,S))
        if cmd == "extract":
            a = extractMax(S)
            print(a)
            
        elif cmd == "end":
            end = True

        elif cmd[0] == "i":
            insert(S,int(cmd[7:]))

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

def extractMax(A):
    x = A[0]
    A[0] = A[-1]
    A.pop()
    H = len(A)
    i = 0
    while i < H: # ???????????????
        v = A[i]
        rv = 0
        lv = 0
        r = (i+1) * 2
        l = r - 1
        if l < H:
            lv = A[l]
            if r < H:
                rv = A[r]

        if v < lv and lv > rv:
            A[l] = v
            A[i] = lv
            i = l
        elif v < rv:
            A[r] = v
            A[i] = rv
            i = r
        else:
            break
    return x

def insert(A, n):
    i = len(A)
    A.append(n)
    while i > 0: # ???????????????
        p = int((i + 1) / 2) - 1
        v = A[i]
        pv = A[p]
        if pv < v: # ???????????§??????
            A[p] = v
            A[i] = pv
            i = p
        else:
            break

def main():
    """ ????????? """
    istr = sys.stdin.read()
    cmds = list(istr.splitlines())

    end = False
    S = []
    for cmd in cmds: # input()
#        print("cmd:{} S:{}".format(cmd,S))
        if cmd[0] == "i":
            insert(S,int(cmd[7:]))

        elif cmd == "extract":
            a = extractMax(S)
            print(a)

        elif cmd == "end":
            end = True
            break


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

import math
import collections
def main():

    N = int(input())
    d = collections.defaultdict(int)

    ans = 0
    for i in range(1, int(math.sqrt(N))+1):
        p = i
        while p <= N:
            d[p] += 1
            if p // i > int(math.sqrt(N)):
                d[p] += 1
            p += i

    for i in range(1, N+1):
        ans += i * d[i]

    return ans

if __name__ == '__main__':
    print(main())

### FIXED CODE ###

import math
import collections
def main():

    N = int(input())
    d = dict()
    for i in range(1, N+1):
        d[i] = 0

    ans = 0
    for i in range(1, N+1):
        p = N//i
        ans += p * (p+1)//2 * i
    return ans

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


n = int(input())
s = input()

ans = n
for i in range(n):
  res = 0
  for j in range(i):
    if s[j] == 'W':
      res += 1
  for k in range(i+1, n):
    if s[k] == 'E':
      res += 1
  ans = min(ans, res)
print(ans)

### FIXED CODE ###

n = int(input())
s = input()

ans = [0]*(n+1)
for i in range(n):
  if s[i] == 'E':
    ans[i+1] = ans[i] + 1
  else:
    ans[i+1] = ans[i]
    
print(min(i-ans[i]+ans[n]-ans[i+1] for i in range(n)))
### BUGGY CODE ###

import itertools
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ans = 0
mod = 10 ** 9 + 7
for l in itertools.combinations(a, k):
    ans += l[-1] - l[0]
    ans %= mod
print(ans)

### FIXED CODE ###

def cmb(n, r, p):
    if r < 0 or n < r:
        return 0
    r = min(r, n - r)
    return fact[n] * fact_inv[r] * fact_inv[n - r] % p


n, k = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
p = 10 ** 9 + 7
fact = [1, 1]  # fact[n] = (n! mod p)
fact_inv = [1, 1]  # fact_inv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # fact_invの計算用

for i in range(2, n + 1):
    fact.append(fact[-1] * i % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    fact_inv.append(fact_inv[-1] * inv[-1] % p)

i = 0
sum_max = 0
sum_min = 0
while n - i - 1 >= k - 1:
    cnt = cmb(n - i - 1, k - 1, p)
    sum_max += a[i] * cnt
    sum_min += a[n - i - 1] * cnt
    # print(i, a[i] * cnt, a[n - i - 1] * cnt)
    i += 1
ans = (sum_max - sum_min) % p
print(ans)
### BUGGY CODE ###

m, n = map(int, input().split())
arr=[]
while abs(m-n) not in arr:
  arr.append(abs(m-n))
  m= abs(m-n)

print(min(arr))
  


### FIXED CODE ###

n, k = map(int, input().split())
print(min(n%k,k-n%k))
### BUGGY CODE ###

def segfunc(x,y):
  return set(x)|set(y)
ide_ele=set()
class SegTree():
  def __init__(self,init_val,segfunc,ide_ele):
    n=len(init_val)
    self.segfunc=segfunc
    self.ide_ele=ide_ele
    self.num=1<<(n-1).bit_length()
    self.tree=[ide_ele]*2*self.num
    for i in range(n):
      self.tree[self.num+i]={init_val[i]}
    for i in range(self.num-1,0,-1):
      self.tree[i]=self.segfunc(self.tree[2*i], self.tree[2*i+1])
  def update(self,k,x):
    k+=self.num
    self.tree[k]=x
    while k>1:
      self.tree[k>>1]=self.segfunc(self.tree[k],self.tree[k^1])
      k>>=1
  def query(self,l,r):
    res=self.ide_ele
    l+=self.num
    r+=self.num
    while l<r:
      if l&1:
        res=self.segfunc(res,self.tree[l])
        l+=1
      if r&1:
        res=self.segfunc(res,self.tree[r-1])
      l>>=1
      r>>=1
    return res
n,q=map(int,input().split())
c=list(map(int,input().split()))
st=SegTree(c,segfunc,ide_ele)
for _ in range(q):
  l,r=map(int,input().split())
  print(len(st.query(l-1,r)))

### FIXED CODE ###

def segfunc(x,y):
  return x+y
ide_ele=0
class SegTree():
  def __init__(self,init_val,segfunc,ide_ele):
    n=len(init_val)
    self.segfunc=segfunc
    self.ide_ele=ide_ele
    self.num=1<<(n-1).bit_length()
    self.tree=[ide_ele]*2*self.num
    for i in range(n):
      self.tree[self.num+i]=init_val[i]
    for i in range(self.num-1,0,-1):
      self.tree[i]=self.segfunc(self.tree[2*i], self.tree[2*i+1])
  def update(self,k,x):
    k+=self.num
    self.tree[k]=x
    while k>1:
      self.tree[k>>1]=self.segfunc(self.tree[k],self.tree[k^1])
      k>>=1
  def query(self,l,r):
    res=self.ide_ele
    l+=self.num
    r+=self.num
    while l<r:
      if l&1:
        res=self.segfunc(res,self.tree[l])
        l+=1
      if r&1:
        res=self.segfunc(res,self.tree[r-1])
      l>>=1
      r>>=1
    return res
n,q=map(int,input().split())
c=list(map(int,input().split()))
st=SegTree([0]*n,segfunc,ide_ele)
lr=[[]for _ in range(n+1)]
for i in range(q):
  l,r=map(int,input().split())
  lr[r]+=[(l,i)]
d={}
for i in range(n):
  if not d.get(c[i]):d[c[i]]=[i]
  else:d[c[i]]+=[i]
for i in d:
  st.update(d[i][-1],1)
ans=[0]*q
r=n
while r>0:
  if lr[r]:
    l,i=lr[r].pop()
    ans[i]=st.query(l-1,r)
  while not lr[r] and r>0:
    if d[c[r-1]]:st.update(d[c[r-1]].pop(),0)
    if d[c[r-1]]:st.update(d[c[r-1]][-1],1)
    r-=1
for i in ans:print(i)
### BUGGY CODE ###

S = input()
s_ex = 'AKIHABARA'

N = len(S) + 1

for i in range(2**N):
    L = [''] * N
    for j in range(N):
        if (i >> j) & 1:
            L[N - j - 1] = 'A'
    # print(L)
    check = ''
    for k in range(N*2-1):
        if k % 2 == 0:
            check += L[k // 2]
        else:
            check += S[k // 2]
    if check == s_ex:
        print('YES')
        exit()

print('NO')

### FIXED CODE ###

import re

S = input()
L = 'A?KIHA?BA?RA?$'

if re.match(L, S):
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from numba import njit


@njit
def loof(a,N,memo):
    M = np.zeros(2019,dtype=np.int16)
    M[0] += 1
    T = 0
    for i in range(N-1,-1,-1):
        T = a[i] * memo[N-i-1] + T
        m = T % 2019
        M[m] += 1
    return M


@njit
def pow_mod(a,n,mod):
    memo = np.array([1])
    if n >= 1:
        for i in range(n-1):
            memo = np.append(memo,memo[-1]*a%mod)
        return memo


def main():
    S = input().rstrip()
    S = list(map(int,list(S)))
    a = np.array(S)

    N = len(a)

    memo = pow_mod(10,N,2019)
    M = loof(a,N,memo)

    res = 0

    for m in M:
        res += m * (m-1) // 2

    print(res)


main()


### FIXED CODE ###

import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from numba import njit, i8


# @njit(i8[:](i8,i8,i8[:]))
@njit
def loof(a,N):
    M = np.zeros(2019,dtype=np.int16)
    M[0] += 1
    T = 0
    r = 1
    T += a[-1] * r
    T %= 2019
    M[T] += 1
    for i in range(N-2,-1,-1):
        r *= 10
        r %= 2019
        T += a[i] * r
        T %= 2019
        M[T] += 1
    return M


# @njit
# def pow_mod(a,n,mod):
#     memo = np.array([1])
#     if n >= 1:
#         for i in range(n-1):
#             memo = np.append(memo,memo[-1]*a%mod)
#         return memo
#     else:
#         return memo[0]


def main():
    S = input().rstrip()
    S = list(map(int,list(S)))
    a = np.array(S)

    N = len(a)

    # memo = pow_mod(10,N,2019)
    M = loof(a,N)

    res = 0

    for m in M:
        res += m * (m-1) // 2

    print(res)


main()
### BUGGY CODE ###

from sys import stdin
n,q = [int(x) for x in stdin.readline().rstrip().split()]
s = stdin.readline().rstrip()
data = [stdin.readline().rstrip().split() for _ in range(q)]
data = [[int(i) for i in l] for l in data]
for d in data:
    sub=s[d[0]-1:d[1]]
    sub=sub.replace('T','').replace('G','')
    print(sub.count('AC'))

### FIXED CODE ###

from sys import stdin
n, q = [int(_) for _ in stdin.readline().rstrip().split()]
s = list(stdin.readline().rstrip())
data = [list(map(int, stdin.readline().rstrip().split())) for _ in range(q)]
l = [0]
for i in range(n):
    l.append(l[i]+1 if i+1 < n and s[i] == 'A' and s[i+1] == 'C' else l[i])
for d in data:
    print(l[d[1]-1]-l[d[0]-1])
### BUGGY CODE ###

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

### FIXED CODE ###

N=int(input())
print(N*(N-1)//2)
### BUGGY CODE ###

n1 = int(input())

r1 = 0
for i1 in range(n1):
    r1 += i1

print(r1)

### FIXED CODE ###

n1 = int(input())

r1 = (n1 * (n1 - 1)) // 2

print(r1)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a = sorted(a, reverse=True)
def find_min_fuka_idx(lst, e1, e2):
  ok = -1
  ng = len(lst)
  while abs(ok-ng)>1:
    mid = (ok+ng)//2
    e3 = lst[mid]
    if e1+e2 > e3 and e2+e3>e1 and e3+e1>e2:
      ok = mid
    else:
      ng = mid
  return ng
c = 0
for i in range(n-2):
  for j in range(i+1, n-1):
    c += find_min_fuka_idx(a[j+1:], a[i], a[j])
print(c)
  

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a = sorted(a, reverse=True)
def find_min_fuka_idx(lst, e1, e2):
  ok = -1
  ng = len(lst)
  while abs(ok-ng)>1:
    mid = (ok+ng)//2
    e3 = lst[mid]
    if e1+e2 > e3 and e2+e3>e1 and e3+e1>e2:
      ok = mid
    else:
      ng = mid
  return ng
c = 0
for i in range(n-2):
  for j in range(i+1, n-1):
    c += find_min_fuka_idx(a[j+1:], a[i], a[j])
print(c)
### BUGGY CODE ###

n, k = map(int, input().split())
if k == 1:
    print(0)
elif k == 2:
    if n % 2 == 0:
        print(0)
    else:
        print(1)
else:
    while n > k:
        n = n-k
    if n < k-n:
        print(n)
    else:
        print(k-n)

### FIXED CODE ###

n, k = map(int, input().split())
if n < k:
    if n < k-n:
        print(n)
    else:
        print(k-n)
else:
    n = n%k
    if n < k-n:
        print(n)
    else:
        print(k-n)
### BUGGY CODE ###

N, K = [int(i) for i in input().split()]
H = [int(i) for i in input().split()]
dp = [0] + [float('inf')]*(N-1)
for j in range(1,N):
    for i in range(max(0,j-K),j):
        dp[j] = min(dp[j],dp[i] + abs(H[j]-H[i]))
print(dp[-1])

### FIXED CODE ###

def func():
    N, K = [int(i) for i in input().split()]
    H = [int(i) for i in input().split()]
    
    dp = [0]*N
    for i in range(1, N):
        L = []
        for j in range(max(0, i-K), i):
            L.append(dp[j] + abs(H[i] - H[j]))
        dp[i] = min(L)

    print(dp[-1])
    
if __name__=="__main__":
    func()
### BUGGY CODE ###

N=int(input())
listn = list(map(int,input().split()))
moji = "YES"

for i in range(N):
  if listn[i] in listn[i+1:]:
    moji = "NO"
    break
  else:
    continue
print(moji)

### FIXED CODE ###

N=int(input())
listn = list(map(int,input().split()))
setn = set(listn)

if len(listn) == len(setn):
  print("YES")
else:
  print("NO")
### BUGGY CODE ###

n = int(input())

# 0, 0+0
# 1, 1+0
# 2, 2+0
# 3, 3+0
# 4, 4+0
# 5, 5+0
# 6, 1+4
# 7, 1+3
# 8, 1+2
# 9, 1+1
# 99, 2枚
# 99999, 2枚...
ans = 0
while n > 0:
    t = n
    pre_t = t
    keta = 0
    while t >= 10:
        pre_t = t
        t //= 10
        keta += 1
    if t < 5 or (t == 5 and pre_t <= 54):  # 555 の時とか1000円だすと14枚で行けてしまう。。
        ans += t
        n = n - t * (10 ** keta)
        #print(t * (10 ** keta),'払った,残り', n, ans)
    else:
        ans += 1
        n = (10 ** (keta + 1)) - n  # どちらがお金を払うかが入れ替わる
        #print((10 ** (keta + 1)),'払った,お釣り', n, ans)
print(ans)

### FIXED CODE ###

n = input()
lenn = len(n)

dp = [0, 10000]
for d in reversed(n):
    d = int(d)
    dp = [min(d + dp[0], d + 1 + dp[1]), min(10 - d + dp[0], 9 - d + dp[1])]

print(min(dp[0], 1 + dp[1]))
### BUGGY CODE ###

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

result=0

for j in range(N-1):
    for k in range(j+1,N):
        if k-j==A[k]+A[j]:
            result +=1

print(result)

### FIXED CODE ###

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

result=0

D={}

for j in range(N):
    if j+A[j] in D:
        D[j+A[j]] += 1
    else:
        D[j+A[j]]=1

for j in range(N):
    if j-A[j] in D:
        result += D[j-A[j]]

print(result)