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

# 試合を頂点とした有向グラフを書く
# 対戦2チームを元に試合ID(頂点番号)に変換できるようにする
# 閉路があるとNGなので-1
# 閉路がない場合は最長経路が答え

import sys
readline = sys.stdin.readline

N = int(readline())

to_id = {}
next_id = 0
def convert_to_id(a,b,next_id):
  if (a,b) not in to_id:
    to_id[(a,b)] = next_id
    to_id[(b,a)] = next_id
    return next_id + 1
  return next_id

G = [[] for i in range((N * (N - 1)) // 2)] # 試合グラフ
indegree = [0 for i in range((N * (N - 1)) // 2)] # 入次数
for i in range(N):
  A = list(map(int,readline().split()))
  cur = None
  for a in A:
    # i と a - 1の試合
    next_id = convert_to_id(i,a - 1,next_id)
    game = to_id[(i,a - 1)]
    if cur != None:
      G[cur].append(game)
      indegree[game] += 1 # 試合に対する入次数が1
    cur = game

done = set()
# 各日付ごとに、入次数が0の試合から行っていく
# 入次数が0になった試合を翌日の試合リスト
stack = []
for i in range(len(indegree)):
  if indegree[i] == 0:
    stack.append(i)

if len(stack) == 0:
  print(-1)
  exit(0)
  
day = 0
while stack:
  day += 1
  nextday = []
  while stack:
    game = stack.pop()
    if game in done: # 既に終わっている試合の場合　閉路と見なす
      print(-1)
      exit(0)
    done.add(game)
    for child in G[game]: # 翌日のゲームを探索
      indegree[child] -= 1
      if indegree[child] == 0: # 入次数が0になれば翌日試合できる
        nextday.append(child)
  stack = nextday

if len(done) != ((N * (N - 1)) // 2):
  print(-1)
  exit(0)
print(day)

### FIXED CODE ###

N=int(input())
a=[[0 for j in range(N-1)] for i in range(N)]
for i in range(N):
  line=list(map(int,input().split()))
  for j in range(N-1):
    a[i][j]=line[j]-1
  a[i]=a[i][::-1]
    
q=[]

#seen=[[False for j in range(N)] for i in range(N)]

# 選手nが試合できるならqueに入れる
def check(i):
  if len(a[i])==0:
    return False
  j=a[i][-1]
  if a[j][-1]==i:
    q.append([i,j])
  
for i in range(N):
  check(i)
  
from collections import defaultdict

day=0
while q:
  day+=1
 # q=sorted(q)
  prevQ=q.copy()
  q=[]
  matched=defaultdict(list)
  for p in prevQ:
    i=p[0]
    j=p[1]
    if i>j:
      i,j=j,i
    if matched[i]:
      continue
    a[i].pop()
    a[j].pop()
    check(i)
    check(j)
    matched[i].append(j)
    
for i in range(N):
  if len(a[i])!=0:
    print(-1)
    break
else:
  print(day)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
#Ai=A[i-1]
s=""
for i in range(N):
    if i!=0:
        s+=" "
#教室にi+1人いたとき
    for j in range(N):
#出席番号i=j+1
        if i+1==A[j]:
            s+="{}".format(j+1)

print(s)


### FIXED CODE ###

from operator import itemgetter

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

print(*[t[0] + 1 for t in sorted(enumerate(A), key=itemgetter(1))])
### BUGGY CODE ###

#import math
N, K = list(map(int, input().strip().split()))

def gcd(a,b):
  a, b = max(a, b), min(a, b)
  while b!=0:
    a,b=b,a%b
  return a

def gcd2(a, b):
  while True:
    if a > b:
      if a % b == 0:
        return 0
      else:
        a = abs(a-b)
    elif a == b:
      return 0
    else:
      return min(a, abs(a-b))

ans = gcd2(N, K)
if ans == K:
  print(0)
else:
  print(ans)

"""
if N < K:
  print(min(N, abs(N-K)))
elif N == K:
  print(0)
else:
  ans = gcd(N, K)
  if ans == K:
    print(0)
  else:
    print(ans)
"""

### FIXED CODE ###

#import math
N, K = list(map(int, input().strip().split()))

def gcd2(a, b):
  while True:
    if a > b:
      if a % b == 0:
        return 0
      else:
        #a = a-b
        a = a % b
    elif a == b:
      return 0
    else:
      return min(a, abs(a-b))

ans = gcd2(N, K)
if ans == K:
  print(0)
else:
  print(ans)
### BUGGY CODE ###

from functools import reduce
n = int(input())
s = list(input())
def count_combination(x):
    if sum(x) != n:
        return(0)
    total_count = 1
    false_count = 0
    for i in range(2*n):
        if x[i]:
            total_count *= false_count
            false_count -= 1
        else:
            false_count += 1
        if false_count == -1:
            return(0)
    return(total_count)
sb = list(map(lambda x: False if x == 'W' else True, s))
sb[::2] = list(map(lambda x: not x, sb[::2]))

total_count = count_combination(sb)

permutation = reduce(lambda x, y: x*y%(10**9+7), range(1,n+1))

print(total_count * permutation % (10**9+7))

### FIXED CODE ###

from functools import reduce
n = int(input())
s = list(input())
def count_combination(x):
    if sum(x) != n:
        return(0)
    total_count = 1
    false_count = 0
    for i in range(2*n):
        if x[i]:
            total_count = total_count*false_count%(10**9+7)
            false_count -= 1
        else:
            false_count += 1
        if false_count == -1:
            return(0)
    return(total_count)
sb = list(map(lambda x: False if x == 'W' else True, s))
sb[::2] = list(map(lambda x: not x, sb[::2]))

total_count = count_combination(sb)

permutation = reduce(lambda x, y: x*y%(10**9+7), range(1,n+1))

print(total_count * permutation % (10**9+7))
### BUGGY CODE ###

import sys
import collections

sys.setrecursionlimit(100000000)


# p:parent
def bfs(g: {}, v: int, p: int, depth: int, dd: {}, dq):
    dd[v] = (p, depth)

    ls = g.setdefault(v, [])
    for next_v in ls:
        # next_v が親だったらスルー
        if next_v == p:
            continue
        # 探索キューに追加
        dq.append((next_v, v, depth+1))


def main():
    n, m = map(int, input().split())

    children = set()
    g = {}
    # parent_g = {}
    for i in range(n - 1 + m):
        a, b = map(int, input().split())
        dic_a = g.setdefault(a - 1, [])
        dic_a.append(b - 1)
        children.add(b - 1)
        # dic_b = parent_g.setdefault(b - 1, [])
        # dic_b.append(a - 1)

    root = -1
    for i in range(n):
        if i not in children:
            root = i
            break
    parent = -1
    depth = 0
    dd = {}

    dq = collections.deque()
    dq.append((root, parent, depth))
    while len(dq) > 0:
        t, p, d = dq.popleft()
        bfs(g, t, p, d, dd, dq)

    for i in range(n):
        print(dd[i][0] + 1)
        # if len(v) == 1:
        #     print(v[0][0]+1)
        #     continue
        #
        # v.sort(key=lambda x: x[1], reverse=True)
        # print(v[0][0]+1)



main()


### FIXED CODE ###

import sys
import collections

sys.setrecursionlimit(100000000)


# p:parent
def bfs(g: {}, parent_g: {}, v: int, p: int, depth: int, dd: {}, dq):
    p_ls = parent_g.setdefault(v, [])
    if len(p_ls) > 1:
        p_ls.remove(p)
        return
    dd[v] = (p, depth)

    ls = g.setdefault(v, [])
    for next_v in ls:
        # next_v が親だったらスルー
        if next_v == p:
            continue
        # 探索キューに追加
        dq.append((next_v, v, depth+1))


def main():
    n, m = map(int, input().split())

    children = set()
    g = {}
    parent_g = {}
    for i in range(n - 1 + m):
        a, b = map(int, input().split())
        dic_a = g.setdefault(a - 1, [])
        dic_a.append(b - 1)
        children.add(b - 1)
        dic_b = parent_g.setdefault(b - 1, [])
        dic_b.append(a - 1)

    root = -1
    for i in range(n):
        if i not in children:
            root = i
            break
    parent = -1
    depth = 0
    dd = {}

    dq = collections.deque()
    dq.append((root, parent, depth))
    while len(dq) > 0:
        t, p, d = dq.popleft()
        bfs(g, parent_g, t, p, d, dd, dq)

    for i in range(n):
        print(dd[i][0] + 1)
        # if len(v) == 1:
        #     print(v[0][0]+1)
        #     continue
        #
        # v.sort(key=lambda x: x[1], reverse=True)
        # print(v[0][0]+1)



main()
### BUGGY CODE ###

def slove():
    import sys
    import copy
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    a = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    ls = [0] * n
    mt = [0] * n
    cnt = 0
    bbb = 0

    for i in range(n):
        if ls[i] != -1:
            mt[i] = a[i][ls[i]]

    it = [i for i in range(n)]

    for w in range(10 ** 15):
        cnt += 1
        bb = False
        update = []
        f = [False] * n
        for i in it:
            if not f[i]:
                if ls[i] != -1:
                    if i + 1 == mt[mt[i]-1]:
                        bb = True
                        f[i] = True
                        f[mt[i]-1] = True
                        if ls[i] + 1 < n - 1:
                            ls[i] += 1
                            update.append(i)
                        else:
                            ls[i] = -1
                            bbb += 1

                        if ls[mt[i]-1] + 1 < n - 1:
                            ls[mt[i]-1] += 1
                            update.append(mt[i]-1)
                        else:
                            ls[mt[i]-1] = -1
                            bbb += 1
        it = copy.deepcopy(update)
        for i in update:
            if ls[i] != -1:
                mt[i] = a[i][ls[i]]
        if bbb == n:
            print(cnt)
            exit()
        if not bb:
            print(-1)
            exit()


if __name__ == '__main__':
    slove()


### FIXED CODE ###

def slove():
    import sys
    import collections
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    a = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    ad = [0] * n
    dq = collections.deque([[0, i + 1] for i in range(n)])
    for i in range(10 ** 15):
        fd = {}
        while True:
            if len(dq) != 0:
                d, q = dq.popleft()
                q -= 1
                if d <= i:
                    if ad[q] < n - 1:
                        qq = a[q][ad[q]] - 1
                        tq = a[qq][ad[qq]] - 1
                        if q == tq and qq not in fd and tq not in fd:
                            ad[qq] += 1
                            ad[tq] += 1
                            if ad[qq] < n - 1:
                                dq.append([d + 1, qq + 1])
                            if ad[tq] < n - 1:
                                dq.append([d + 1, tq + 1])
                            fd[qq] = 0
                            fd[tq] = 0
                else:
                    dq.append([d, q + 1])
                    break
            else:
                break
        if len(dq) == 0:
            b = True
            for v in ad:
                if v != n - 1:
                    b = False
                    break
            if b:
                print(i + 1)
                exit()
            else:
                print(-1)
                exit()


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

n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [0] * n
t = []
 
for i in range(1,n):
    for l in range(1,k+1):
        if i - l >= 0:
            t.append(abs(h[i] - h[i-l]) + dp[i-l])
        else:
            break
 
    dp[i] = min(t)
    t.clear()

print(dp[-1])

#実行制限時間2秒以内に間に合わない

### FIXED CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [0] * n
t = []
 
for i in range(1,n):
    for l in range(1,k+1):
        if i - l >= 0:
            t.append(abs(h[i] - h[i-l]) + dp[i-l])
        else:
            break
    dp[i] = min(t)
    t.clear()
 
print(dp[-1])
### BUGGY CODE ###

# coding: utf-8
import sys

input = sys.stdin.readline

N, Q = map(int, input().split())
S = input().strip()

tile = {} # 文字マップ
now = [1] * N

for s in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
  tile.setdefault(s, [])

for i in range(len(S)):
  tile[S[i]].append(i)

for i in range(Q):
  t, d = input().split()
  if d == "L":
    for j in tile[t]:
      if j != 0:
        now[j-1] += now[j]
      now[j] = 0
  else:
    for j in tile[t]:
      if j != N-1:
        now[j+1] += now[j]
      now[j] = 0

print(sum(now))

### FIXED CODE ###

# coding: utf-8
import sys

input = sys.stdin.readline

N, Q = map(int, input().split())
S = input().strip()
td_list = [input().split() for _ in range(Q)]
dest = [-2] * (N+1)

def sim(i): # i番目のゴーレムの最終結果を得る
  idx = i
  if dest[i] != -2:
    return dest[i]
  for td in td_list:
    if idx == -1:
      dest[i] = -1
      return -1
    elif idx == N:
      dest[i] = N
      return N
    elif td[0] == S[idx]:
      if td[1] == "L":
        idx -= 1
      else:
        idx += 1
  dest[i] = idx
  return idx


# 左側の境界を探索
left, right = -1, N

while right - left != 1:
  mid = (left + right) // 2
  if sim(mid) == -1:
    left = mid
  else:
    right = mid

lb = right

# 右側の境界を探索
left, right = -1, N

while left+1 < right:
  mid = (left + right) // 2
  if sim(mid) == N:
    right = mid
  else:
    left = mid

rb = left

print(rb - lb + 1)
### BUGGY CODE ###

from itertools import permutations

N,M,R=map(int,input().split())
*r,=map(int,input().split())
inf=float("inf")
d=[[inf]*N for _ in range(N)]

for _ in range(M):
    A,B,C=map(int,input().split())
    d[A-1][B-1]=C
    d[B-1][A-1]=C

for k in range(N):
    for i in range(N):
        for j in range(N):
            d[i][j]=min(d[i][j],d[i][k]+d[k][j])

ans=inf
for i in permutations(r):
    v=0
    for j in range(R-1):
        v+=d[i[j]-1][i[j+1]-1]
    ans=min(ans,v)

print(ans)

### FIXED CODE ###

from itertools import permutations as p
N,M,R=map(int,input().split())
r=map(int,input().split())
inf=float("inf")
l=[[inf if i!=j else 0 for i in range(N)] for j in range(N)]

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

for k in range(N):
  for i in range(N):
    for j in range(N):
      l[i][j]=min(l[i][j],l[i][k]+l[k][j])

ans=inf
for i in p(r):
  v=0
  for j in range(R-1):
    v+=l[i[j]-1][i[j+1]-1]
  ans=min(ans,v)
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
A = [int(x) for x in input().split()]
A = sorted(A)[::-1]
res = 0
for x in A:
    res += x
for m in range(M):
    tmp = sorted(A[:m+1])[::-1]
    k = tmp[0]
    tmp[0] = int(tmp[0]/2)
    l = tmp[0]
    tmp.extend(A[m+1:])
    A = tmp
    res -= k-l

print(res)


### FIXED CODE ###

from heapq import *
N, M = map(int, input().split())
A = [-int(x) for x in input().split()]
heapify(A)
for x in range(M):
    tmp = int(heappop(A)/2)
    heappush(A,tmp)
res = 0
for x in A:
    res -= x
print(res)
### BUGGY CODE ###

def Z_algo(S):
    n = len(S)
    LCP = [0]*n
    i = 1
    j = 0
    c = 0
    for i in range(1, n):
        if i+LCP[i-c] < c+LCP[c]:
            LCP[i] = LCP[i-c]
        else:
            j = max(0, c+LCP[c]-i)
            while i+j < n and S[j] == S[i+j]: j+=1
            LCP[i] = j
            c = i
    LCP[0] = n
    return LCP

def main():
    n = int(input())
    s = input().rstrip()
    ans = 0
    for i in range(n):
        lcp = Z_algo(s[i:])
        for j, l in enumerate(lcp):
            x = min(l, j)
            ans = max(ans, x)
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def check(x, N, S):
    candidate = set()
    for i in range(N - 2*x + 1):
        candidate.add(S[i:i+x])
        if S[i+x:i+2*x] in candidate:
            return True
    return False

def main():
    n = int(input())
    s = input().rstrip()
    l = 0
    r = n
    while l < r:
        mid = (l+r+1) // 2
        if check(mid, n, s):
            l = mid
        else:
            r = mid-1
    print((l+r+1)//2)

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

from collections import defaultdict as dd
road = dd(list)
train = dd(list)
rd = dict()
td = dict()
ans = []
def gr(tree,start):
    island = set()
    rest = [start,]
    while rest:
        node = rest.pop()
        island.add(node)
        for x in tree[node]:
            if x not in island:
                rest.append(x)
    return(island)
n,k,l = map(int, input().split())
for _ in range(k):
    a,b = map(int, input().split())
    road[a].append(b)
    road[b].append(a)
for _ in range(l):
    a,b = map(int, input().split())
    train[a].append(b)
    train[b].append(a)
for i in range(1,n+1):
    if i not in rd:
      tempr = gr(road,i)
      for x in tempr:
        rd[x] = tempr
    if i not in td:
      tempt = gr(train,i)
      for x in tempt:
        td[x] = tempt
    ans.append(str(len(rd[i]&td[i])))
print(" ".join(ans))

### FIXED CODE ###

from collections import defaultdict as dd
def find(u,x):
    if u[x]<0:
        return x
    u[x] = find(u,u[x])
    return u[x]

def unite(u,a,b):
    a = find(u,a)
    b = find(u,b)
    if a == b:
        return False
    if u[b] < u[a]:
        a,b = b,a
    u[a] += u[b]
    u[b] = a
    return True
n,k,l = map(int, input().split())
ufr = [-1]*(n+1)
uft = [-1]*(n+1)
for _ in range(k):
    a,b = map(int, input().split())
    unite(ufr,a,b)
for _ in range(l):
    a,b = map(int, input().split())
    unite(uft,a,b)
tot = dd(int)
for i in range(1,n+1):
  tot[(find(ufr,i),find(uft,i))] += 1
print(" ".join([str(tot[(find(ufr,i),find(uft,i))]) for i in range(1,n+1)]))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
A.sort()
cnt = 0
onaji = 0

#数列Aを昇順に並べ替えた後、AjがAiの倍数になっていた時Ajをリストから削除する方針です。
for i in range(len(A)):
    if i >= len(A)-1: #数列が小さくなって行くので当初のループ量は必要ないので。
        break
    for j in range(len(A)-1,i,-1): #大きい数字から順番にみていく。
        if A[i] == A[j]:
            onaji = 1
        if A[j] % A[i] == 0:
            del A[j]
            
    if onaji == 1: #同じ数字があった時Aiも削除。
        del A[i]
        onaji = 0

print(len(A))


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
OKlist = [0]*(10**6+100)
A.sort()
for i in range(len(A)-1):
    if A[i] == A[i+1]:
        OKlist[A[i]] += 1
    else:
        for j in range(10**6+10):
            if A[i]*j > 10**6:
                break
            else:
                OKlist[A[i]*j] += 1
OKlist[max(A)] += 1
cnt = 0
for i in A:
    if OKlist[i] == 1:
        cnt += 1
        
print(cnt)
### BUGGY CODE ###

import numpy as np
n, a = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]

dp= np.zeros((n+1,n+1,n*a+1),dtype=int)
dp[0][0][0]=1
ans=0

for k in range(1,n+1):
  for i in range(0,k+1):
    for j in range(0,a*n+1):
      if j>=x[k-1] and i>=1:
        dp[k][i][j]= dp[k-1][i][j] + dp[k-1][i-1][j-x[k-1]]
      else:
        dp[k][i][j]= dp[k-1][i][j] 
      
for i in range(1,n+1):
  ans+=dp[n][i][a*i]

print(ans)

### FIXED CODE ###

n, a = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]

dp=[[0 for i in range(a*n+1)] for j in range(n+1)]
dp[0][0]=1
ans=0
f=0

for k in range(1,n+1):
  kx=x[k-1]
  f+=kx
  for i in range(k,0,-1):
    for j in range(kx,a*n+1):
      dp[i][j] += dp[i-1][j-kx]
      if j > f:
        break
      
for i in range(1,n+1):
  ans+=dp[i][a*i]

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

from collections import deque

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

F=[[] for _ in range(N)]
B=[[] for _ in range(N)]


for i in range(M):
    a,b=map(int,input().split())
    F[a-1].append(b-1)
    F[b-1].append(a-1)

for i in range(K):
    a,b=map(int,input().split())
    B[a-1].append(b-1)
    B[b-1].append(a-1)

q=deque([])
G=[]
visited=[0]*N
for i in range(N):
    if visited[i]==1:continue
    visited[i]=1
    q.append([i,[i]])
    while q:
        n,c=q.pop()
        for j in F[n]:
            if visited[j]==0:
                c.append(j)
                visited[j]=1
                q.append([j,c])
    G.append(c)

ans=[0]*N

for g in G:
    for i in g:
        cnt=0
        for j in B[i]:
            if j in g:
                cnt+=1
        ans[i]=len(g)-len(F[i])-cnt-1

for i in ans:
    print(str(i),end=" ")


### FIXED CODE ###

from collections import deque

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

F=[[] for _ in range(N)]
B=[[] for _ in range(N)]


for i in range(M):
    a,b=map(int,input().split())
    F[a-1].append(b-1)
    F[b-1].append(a-1)

for i in range(K):
    a,b=map(int,input().split())
    B[a-1].append(b-1)
    B[b-1].append(a-1)

q=deque([])
G=[]
visited=[0]*N
group=[-1]*N
idx=0
for i in range(N):
    if visited[i]==1:continue
    visited[i]=1
    group[i]=idx
    q.append([i,[i]])
    while q:
        n,c=q.pop()
        for j in F[n]:
            if visited[j]==0:
                c.append(j)
                visited[j]=1
                group[j]=idx
                q.append([j,c])
    G.append(c)
    idx+=1

cnt=[0]*N
for g in G:
    for i in g:
        for b in B[i]:
            if  group[i]==group[b]:
                cnt[i]+=1

ans=[0]*N

for g in G:
    for i in g:
        ans[i]=len(g)-len(F[i])-cnt[i]-1

for i in ans:
    print(str(i),end=" ")
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
tmpA = [1 for i in range(N)]
tmpB = []

for i in range(K):
    tmpA = [1 for i in range(N)]
    tmpB = []
    for j in range(N):
        tmpA[j] += len(tmpB)
        tmpB = list(filter(lambda x:x, map(lambda x:x-1, tmpB)))
        if A[j]:
            tmpB.append(A[j])

    
    tmpB = []
    for j in range(N - 1, -1 ,-1):
        tmpA[j] += len(tmpB)
        tmpB = list(filter(lambda x:x, map(lambda x:x-1, tmpB)))
        if A[j]:
            tmpB.append(A[j])
            
    A = tmpA

[print(i, end=' ') for i in A]
print()


### FIXED CODE ###

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

for i in range(min(K, 50)):
    B = [0 for i in range(N)]
    for j in range(0, N):
        l = max(0, j - A[j])
        r = min(N - 1, j + A[j])
        B[l] += 1
        if r + 1 < N:
            B[r + 1] -= 1

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

[print(i, end=' ') for i in B]
print()
### BUGGY CODE ###

n,k=map(int,input().split())
l=list(map(int,input().split()))
dp=[0 for t in range(n)]
if k+1>=n:
  print(abs(l[-1]-l[0]))
  exit()
for i in range(n)[1:]:
  a=float('inf')
  for d in range(min(i,k)+1)[1:]:
    a=min(a,dp[i-d]+abs(l[i]-l[i-d]))
  dp[i]=a
print(dp[-1])

### FIXED CODE ###

n,k=map(int,input().split())
dp=[10**10]*n
h=list(map(int,input().split()))
dp[0]=0
for i in range(1,n):
    dp[i]=min(dp[i-j]+abs(h[i-j]-h[i]) for j in range(1,1+min(k,i)))

print(dp[-1])
### BUGGY CODE ###

def s():
  from sys import stdin
  read=stdin.buffer.readline
  n=int(read())
  l=list(map(int,read().split()))
  f=l[0]
  mod=10**9+7
  def gcd(s,d):
    s,d=max(s,d),min(s,d)
    while  d:
      s,d=d,s%d
    return s
  for i in l:
    f=i*f//gcd(i,f)
  ans=0
  for iu in l:
    ans+=(f//iu)%mod
    ans%=mod
  print(ans)
  
if __name__=="__main__":s()

### FIXED CODE ###

def s():
  from sys import stdin
  read=stdin.buffer.readline
  n=int(read())
  l=list(map(int,read().split()))
  f=l[0]
  mod=10**9+7
  def gcd(s,d):
    s,d=max(s,d),min(s,d)
    while  d:
      s,d=d,s%d
    return s
  for i in l:
    f=i*f//gcd(i,f)
  ans=0
  for iu in l:
    b,u,v=mod,1,0
    while b:
      t=iu//b;iu,b=b,iu%b;u-=t*v;u,v=v,u
    ans+=(f*u%mod)%mod
    ans%=mod
  print(ans)
  
if __name__=="__main__":s()
### BUGGY CODE ###

N,K = [int(x) for x in input().split()]
h = [int(x) for x in input().split()]
DP=[1000000000]*(N+1)
DP[0] = 0
DP[1] = 0
DP[2] = DP[1] + abs(h[0]-h[1])
for i in range(1,N):
    for j in range(i+1,min(i+K+1,N+1)):
        DP[j] = min(DP[j],DP[i]+abs(h[j-1]-h[i-1]))
print(DP[N])

### FIXED CODE ###

N,k = [int(x) for x in input().split()]
h = [int(x) for x in input().split()]
DP = [1000000000]*N
DP[0] = 0
def handan(i,x):
    if DP[i] > x:
        DP[i] = x
for i in range(1,N):
    for j in range(min(i,k)):
        x = DP[i-j-1] + abs(h[i]-h[i-j-1])
        handan(i,x)
print(DP[N-1])
### BUGGY CODE ###

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

### FIXED CODE ###

n = int(input())
a = list(map(int ,input().split()))
ans = 1
if 0 in a:
  print(0)
  exit()
for i in range(n):
  ans *= a[i]
  if ans > 10**18:
    print(-1)
    exit()
print(ans)
### BUGGY CODE ###

A, B, C, K = map(int, input().split())
for i in range(K):
	temp_a = A
	temp_b = B
	A = B + C
	B = temp_a + C
	C = temp_a + temp_b
if abs(A - B) <= 10 ** 18:
	print(A - B)
else:
	print("Unfair")

### FIXED CODE ###

A, B, C, K = map(int, input().split())
if K % 2 != 0:
	res = B - A
else:
	res = A - B
if res >= 10 ** 18:
	print("Unfair")
else:
	print(res)
### BUGGY CODE ###

N = int(input())
S = list( input("") )
A = list(set(S))
result = []
for i in A:
    for j in range(S.index(i)+1 , N):
        for k in range(j+1, N):
            result.append(i + S[j] + S[k])
c = list(set(result))
print(len(c))

### FIXED CODE ###

N = int(input())
S = list( input("") )
A =  set(S)
count = 0
for i in A:
    b = S.index(i) + 1
    B = set(S[b:])
    for j in B:
        c = S[b:].index(j) + 1
        C = set(S[b:][c:])
        count += len(C)
print(count)