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

import numpy as np
import sys
input = sys.stdin.readline
def main():
    r,c,k=map(int,input().split())
    a=[list(map(int,input().split())) for _ in range(k)]
    dp=np.array([[[0,0,0,0,0]for _ in range(c+1)]for _ in range(r+1)])
    b=[[0 for _ in range(c+1)] for _ in range(r+1)]
    for x,y,z in a:
        b[x][y]=z
    for i in range(1,r+1):
        for j in range(1,c+1):
            v=b[i][j]
            if b==0:
                dp[i][j][0]=max(dp[i][j-1][0],dp[i-1][j][0],dp[i-1][j][1],dp[i-1][j][2],dp[i-1][j][3])
                dp[i][j][1]=dp[i][j-1][1]
                dp[i][j][2]=dp[i][j-1][2]
                dp[i][j][3]=dp[i][j-1][3]
            else:
                dp[i][j][0]=max(dp[i][j-1][0],dp[i-1][j][0],dp[i-1][j][1],dp[i-1][j][2],dp[i-1][j][3])
                dp[i][j][1]=max(dp[i][j-1][1],dp[i][j-1][0]+v,dp[i-1][j][0]+v,dp[i-1][j][1]+v,dp[i-1][j][2]+v,dp[i-1][j][3]+v)
                dp[i][j][2]=max(dp[i][j-1][2],dp[i][j-1][1]+v)
                dp[i][j][3]=max(dp[i][j-1][3],dp[i][j-1][2]+v)
    print(max(dp[i][j]))

if __name__ == "__main__":
    main()

### FIXED CODE ###

r,c,k=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(k)]
dp=[[[0 for _ in range(c+1)]for _ in range(r+1)]for _ in range(5)]
for x,y,z in a:
    dp[4][x][y]=z
for i in range(1,r+1):
    for j in range(1,c+1):
        v=dp[4][i][j]
        dp[0][i][j]=max(dp[0][i][j-1],dp[0][i-1][j],dp[1][i-1][j],dp[2][i-1][j],dp[3][i-1][j])
        dp[1][i][j]=max(dp[1][i][j-1],dp[0][i][j-1]+v,dp[0][i-1][j]+v,dp[1][i-1][j]+v,dp[2][i-1][j]+v,dp[3][i-1][j]+v)
        dp[2][i][j]=max(dp[2][i][j-1],dp[1][i][j-1]+v)
        dp[3][i][j]=max(dp[3][i][j-1],dp[2][i][j-1]+v)
print(max([dp[i][r][c] for i in range(4)]))
### BUGGY CODE ###

mod = 10 ** 9 + 7

def comb(n,k,p=mod):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p


def power_func(a,b,p=mod):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p


n, k = map(int, input().split())
A = list(map(int, input().split()))

A.sort()

mini_count = 0
maxim_count = 0

for i in range(n-k+1):
    mini = A[i]
    pattern = comb(n-i-1, k-1)
    mini_count += mini * pattern % mod
    mini_count %= mod


for i in range(1, n-k+2):
    maxim = A[-i]
    pattern = comb(n-i, k-1)
    maxim_count += maxim * pattern % mod
    maxim_count %= mod

ans = maxim_count - mini_count
ans %= mod

print(ans)


### FIXED CODE ###

P = 10**9 + 7
N = 1000000
inv_t = [0]+[1]
for i in range(2,N):
    inv_t += [inv_t[P % i] * (P - int(P / i)) % P]



n, k = map(int, input().split())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7

A.sort()

mini_count = 0
maxim_count = 0
pattern = 1
for i in range(n-k, -1, -1):
    mini = A[i]
    mini_count += mini * pattern % mod
    mini_count %= mod
    pattern = pattern * (n-i) * inv_t[n-i-k+1] % mod


pattern = 1
for i in range(n-k+1, 0, -1):
    maxim = A[-i]
    maxim_count += maxim * pattern % mod
    maxim_count %= mod
    pattern = pattern * (n-i+1) * inv_t[n-i-k+2] % mod

ans = maxim_count - mini_count
ans %= mod

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

mod = 998244353
rng = 300100
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod
n,a,b,k = map(int,input().split())
pair = []
for i in range(n+1):
  if (k-a*i)%b == 0 and (k-a*i)//b <= n:
    pair.append((i,(k-a*i)//b))
ans = 0
for x,y in pair:
  ans = (ans+cmb(n,x)*cmb(n,y))%mod
print(ans)

### FIXED CODE ###

mod = 998244353
rng = 300100
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod
n,a,b,k = map(int,input().split())
pair = []
for i in range(n+1):
  if (k-a*i)%b == 0 and (k-a*i)//b <= n:
    pair.append((i,(k-a*i)//b))
ans = 0
for x,y in pair:
  ans = (ans+cmb(n,x)*cmb(n,y))%mod
print(ans)
### BUGGY CODE ###

import math

n,m = map(int, input().split())

x=math.floor(m/n)

ans=[]
for i in range(1,x+1):
  if(m % i==0):
    ans.append(i)
    
print(ans[-1])

### FIXED CODE ###

import math

n,m = map(int, input().split())

x=int(math.sqrt(m))

ans=1
for i in range(1,x+1):
  if m%i==0:
    if i*n<=m:
      ans=max(ans,i)
    if int(m/i)*n<=m:
      ans=max(ans,int(m/i))
print(ans)
### BUGGY CODE ###

l,r = map(int,input().split())
number_list=[i for i in range(l,r+1)]
result=[]
for i in number_list:
  if i%2019==0:
    print(0)
    break
else:
  for j in number_list:
    for k in number_list:
      if j<k:
        result.append((j*k)%2019)
  print(min(result))
        

### FIXED CODE ###

l,r = map(int,input().split())
c=2019
for i in range(l,r+1):
  if i%2019==0:
    print(0)
    break
else:
  for j in range(l,r+1):
    for k in range(j+1,r+1):
      if c>(j*k%2019):
        c=(j*k%2019)
  print(c)
### BUGGY CODE ###

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

mn = N
while (True):
    N = abs(N - K)
    if mn > N:
        mn = N
    else:
        break

print(mn)


### FIXED CODE ###

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


a = N % K
print(a) if a < abs(a-K) else print(abs(a-K))
### BUGGY CODE ###

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

count = 0

for i in range(N):
    for j in range(i+A[i], N):
        if A[i] + A[j] == abs(i-j):
            count += 1

print(count)


### FIXED CODE ###

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

count = 0

for i in range(N):
    l = i + A[i]
    r = i - A[i]
    if r in L.keys():
        count += L[r]
    if l in L.keys():
        L[l] += 1
    else:
        L[l] = 1
print(count)
### BUGGY CODE ###

H,W=[int(s) for s in input().split()]
lamp=[input() for _ in range(H)]
#Lを計算
L=[[0 for _ in range(W)] for _ in range(H)]
for i in range(H):
  if lamp[i][0]=="#" :  L[i][0]=0
  else: L[i][0]=1
  for j in range(1,W):
    if lamp[i][j]=="#" : L[i][j]=0
    else: L[i][j]=L[i][j-1]+1
#Rを計算
R=[[0 for _ in range(W)] for _ in range(H)]
for i in range(H):
  if lamp[i][W-1]=="#" :  R[i][W-1]=0
  else: R[i][W-1]=1
  for j in range(1,W):
    if lamp[i][W-1-j]=="#" : R[i][W-1-j]=0
    else: R[i][W-1-j]=R[i][W-j]+1
#Uを計算
U=[[0 for _ in range(W)] for _ in range(H)]
for j in range(W):
  if lamp[0][j]=="#" :  U[0][j]=0
  else: U[0][j]=1
  for i in range(1,H):
    if lamp[i][j]=="#" : U[i][j]=0
    else: U[i][j]=U[i-1][j]+1
#Dを計算
D=[[0 for _ in range(W)] for _ in range(H)]
for j in range(W):
  if lamp[H-1][j]=="#" :  D[H-1][j]=0
  else: D[H-1][j]=1
  for i in range(1,H):
    if lamp[H-1-i][j]=="#" : D[H-1-i][j]=0
    else: D[H-1-i][j]=D[H-i][j]+1
ls=[]
for i in range(H):
  for j in range(W):
    ls.append(L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)
print(max(ls))

### FIXED CODE ###

H,W=[int(s) for s in input().split()]
lamp=[input() for _ in range(H)]
#Lを計算
L=[[0 for _ in range(W)] for _ in range(H)]
for i in range(H):
  if lamp[i][0]=="#" :  L[i][0]=0
  else: L[i][0]=1
  for j in range(1,W):
    if lamp[i][j]=="#" : L[i][j]=0
    else: L[i][j]=L[i][j-1]+1
#Rを計算
R=[[0 for _ in range(W)] for _ in range(H)]
for i in range(H):
  if lamp[i][W-1]=="#" :  R[i][W-1]=0
  else: R[i][W-1]=1
  for j in range(1,W):
    if lamp[i][W-1-j]=="#" : R[i][W-1-j]=0
    else: R[i][W-1-j]=R[i][W-j]+1
#Uを計算
U=[[0 for _ in range(W)] for _ in range(H)]
for j in range(W):
  if lamp[0][j]=="#" :  U[0][j]=0
  else: U[0][j]=1
  for i in range(1,H):
    if lamp[i][j]=="#" : U[i][j]=0
    else: U[i][j]=U[i-1][j]+1
#Dを計算
D=[[0 for _ in range(W)] for _ in range(H)]
for j in range(W):
  if lamp[H-1][j]=="#" :  D[H-1][j]=0
  else: D[H-1][j]=1
  for i in range(1,H):
    if lamp[H-1-i][j]=="#" : D[H-1-i][j]=0
    else: D[H-1-i][j]=D[H-i][j]+1
ls=[]
for i in range(H):
  for j in range(W):
    ls.append(L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)
print(max(ls))
### BUGGY CODE ###

import sys

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

for i in range(N):
    a = a*A[i]
    
if a > 10**18 :
    print(-1)    
else : print(a)



### FIXED CODE ###

import sys

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

if 0 in A :
    print(0)
    sys.exit()

for i in range(N):
    a = a*A[i]
    if a > 10**18 :
        print(-1)    
        sys.exit()

else : print(a)
### BUGGY CODE ###

n = int(input())
s = input()
left = 0
right = n // 2 + 1
while right - left > 1:
    mid = (right + left) // 2
    len = mid
    for i in range(n-2*len + 1):
        s1 = s[i:i+len]
        s2 = s[i+len:]
        if s1 in s2:
            left = mid
            break
    else:
        right = mid
print(left)

### FIXED CODE ###

N = int(input())
S = input()
ok, ng = 0, N + 1
while abs(ok - ng) > 1:
    x = (ok + ng) // 2
    check = set()
    for i in range(N - x + 1):
        check.add(S[i: i + x])
        if S[i + x: i + 2 * x] in check:
            ok = x
            break
    else:
        ng = x

print(ok)
### BUGGY CODE ###

def ncr(n,r):
  if r==0 or n==r:
    return 1
  if r==1 or r==n-1:
    return n
  dp=[[0 for i in range(r+1)] for j in range(n+1)]
  for i in range(n+1):
    dp[i][0]=1
  dp[1][1]=1
 
  for i in range(2,n+1):
    for j in range(1,r+1):
      dp[i][j]=dp[i-1][j-1]+dp[i-1][j]
  return dp[n][r]

n,k=map(int,input().split())
for i in range(1,k+1):
  ans=ncr(n-k+1,i)*ncr(k-1,i-1)
  while ans>10**9+7:
    ans%=10**9+7
  print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
dp=[[0 for i in range(k+1)] for j in range(n+1)]
for i in range(n+1):
  dp[i][0]=1
dp[1][1]=1
for i in range(2,n+1):
  for j in range(1,k+1):
    dp[i][j]=dp[i-1][j-1]+dp[i-1][j]
for i in range(1,k+1):
  ans=dp[n-k+1][i]*dp[k-1][i-1]
  while ans>10**9+7:
    ans%=10**9+7
  print(ans)
### BUGGY CODE ###

M = 10**9+7
N = int(input())
A = list(map(int,input().split()))

ans = 0
for k in range(60):
    N1 = 0
    for a in A:
        if (a >> k) & 1:
            N1 += 1
    N0 = N-N1
    ans += (((1<<k)) *N0 *N1)
    ans %= M    

print(int(ans))

### FIXED CODE ###

M = 10**9+7
N = int(input())
A = list(map(int,input().split()))

ans = 0
for k in range(61):
    N1 = 0
    N1 = sum([1 for a in A if ( (a >> k) & 1)])
    ans += (((1<<k)) *(N-N1) *N1)
    ans %= M    

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

n, m = map(int, input().split())
p = []
s = []
for i in range(m):
    input_p, input_s = input().split()
    p.append(int(input_p))
    s.append(input_s)

ac_list = []
wa_list = [0] * n
wa_count = 0
for i in range(m):
    if p[i] not in ac_list:
        if s[i] == 'AC':
            ac_list.append(p[i])
            wa_count += wa_list[p[i]-1]
        else:
            wa_list[p[i]-1] += 1
print(len(ac_list), wa_count)

### FIXED CODE ###

n, m = map(int, input().split())
ps = [[0, 0] for i in range(n)]  
wa_count = 0
ac_count = 0
for i in range(m):
    input_p, input_s = input().split()
    if ps[int(input_p)-1][0] <= 0:
        if input_s == 'AC':
            ps[int(input_p)-1][0] += 1
        else:
            ps[int(input_p)-1][1] += 1
for i in ps:
    if i[0] == 1:
        ac_count += 1
        wa_count += i[1]

print(ac_count, wa_count)
### BUGGY CODE ###

n=int(input())
a_li=[]
for i in range(n):
    a=int(input()) 
    a_li.append(a)
for i in range(n):
    b=max(a_li)
    if b>a_li[i]:
        ans=b
    else:
        if a_li.count(b)>1:
            ans=b
        else:
            a_li.remove(b)
            ans=max(a_li)
            a_li.insert(i,b)
    print(ans)
        
        

### FIXED CODE ###

n = int(input())
A = [int(input()) for i in range(n)]

M = max(A)
ind = A.index(M)
A[ind] = 0
M2 = max(A)


if M in A:
    for i in range(n):
        print(M)
else:
    for i in range(n):
        if A[i] == 0:
            print(M2)
        else:
            print(M)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
m = max(a)
for i in range(n):
    if m == a[i]:
        a[i] = 0
        ans = max(a)
        a[i] = m
    else:
        ans = m
    print(ans)

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
b = sorted(a,reverse=True)
for i in range(n):
    if b[0] == a[i]:
        ans = b[1]
    else:
        ans = b[0]
    print(ans)
### BUGGY CODE ###

import itertools

n, m, R = [int(i) for i in input().split()]
r = [int(i) - 1 for i in input().split()]
dis = [[float("inf") for _ in range(n)] for _ in range(n)]
for i in range(m):
    a, b, c = [int(i) for i in input().split()]
    dis[a - 1][b - 1] = c
    dis[b - 1][a - 1] = c

# 全ての頂点間の最短距離を算出、
for k in range(len(dis)):
    for i in range(len(dis)):
        for j in range(len(dis)):
            if dis[i][j] > dis[i][k] + dis[k][j]:
                dis[i][j] = dis[i][k] + dis[k][j]


_min = float("inf")
it = itertools.permutations(r)
for iterR in it:
    _dis = 0
    start = iterR[0]
    for end in iterR[1:]:
        _dis += dis[start][end]
        start = end
    _min = min(_min, _dis)
print(_min)

"""
print("2 vs "+func(3, 3, [0, 1, 2], [[0, 1, 4], [1, 0, 1], [4, 1, 0]]))
print("4 vs "+func(3, 3, [0, 2], [[0, 2, 6], [2, 0, 2], [6, 2, 0]]))
print("3 vs "+func(4, 6, [1, 2, 3], [[0, 4, 6, 1], [4, 0, 3, 2], [6, 3, 0, 1], [1, 2, 1, 0]]))
# print("print(func({}, {}, {}, {}))".format(n, m, r, adj))
"""


### FIXED CODE ###

import itertools
n, m, R = map(int, input().split())
r = list(map(int, input().split()))
dis = [[float("inf") for _ in range(n)] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    dis[a - 1][b - 1] = c
    dis[b - 1][a - 1] = c

def war(dis):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dis[i][j] > dis[i][k] + dis[k][j]:
                    dis[i][j] = dis[i][k] + dis[k][j]
    return dis
dis = war(dis)
_min = float("inf")
it = itertools.permutations(r)
for iterR in it:
    _dis = 0
    start = iterR[0] - 1
    for end in iterR[1:]:
        _dis += dis[start][end - 1]
        start = end - 1
    _min = min(_min, _dis)
print(_min)
### BUGGY CODE ###

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

A = [0] * (n + 1)
for i in range(1, n + 1):
    A[i] = A[i - 1] + a[i - 1]

B = [0] * (m + 1)
for i in range(1, m + 1):
    B[i] = B[i - 1] + b[i - 1]

ans = 0
for i in range(n + 1):
    for j in range(m + 1):
        t = A[i] + B[j]
        if t > k:
            break
        else:
            ans = max(ans, i + j)

print(ans)


### FIXED CODE ###

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

A = [0] * (n + 1)
for i in range(1, n + 1):
    A[i] = A[i - 1] + a[i - 1]

B = [0] * (m + 1)
for i in range(1, m + 1):
    B[i] = B[i - 1] + b[i - 1]

ans = 0
best = m
for i in range(n + 1):
    for j in range(best, -1, -1):
        t = A[i] + B[j]
        if t <= k:
            ans = max(ans, i + j)
            best = j
            break
print(ans)
### BUGGY CODE ###

import numpy as np
n = int(input())
a = np.array(list(map(int, input().split())), dtype=np.int64)
mod = 10 ** 9 + 7
ans = [0] * 60
for x in a:
    x = bin(x)[2:].zfill(60)
    for i in range(60):
        ans[i] += int(x[i])
for i in range(60):
    ans[i] = ans[i] * (n - ans[i]) % mod
    ans[i] = ans[i] * pow(2, 59 - i, mod) % mod
ans_sum = 0
for x in ans:
    ans_sum = (ans_sum + x) % mod
print(ans_sum)

### FIXED CODE ###

import numpy as np
import sys
n = int(input())
a = np.array(sys.stdin.read().split(), dtype=np.int64)
mod = 10 ** 9 + 7
ans = 0
for i in range(63):
    b = (a >> i) & 1
    x = np.count_nonzero(b)
    x = x * (n - x)
    ans += x * pow(2, i, mod) % mod
print(ans % mod)
### BUGGY CODE ###

N = int(input())
A_list = list(map(int, input().split()))
A_list.sort()
A_list.insert(0,0)
sum = 0
for i in range(1, N):
    for j in range(i + 1, N + 1):
        sum += (A_list[i] * A_list[j]) 
print(sum% 1000000007)

### FIXED CODE ###

N = int(input())
A_list = list(map(int, input().split()))
A_list.insert(0, 0)

cum_sum = 0
cum_sum_list = []
for i in range(N + 1):
    cum_sum += A_list[i]
    cum_sum_list.append(cum_sum)

ans = 0
for i in range(1, N+1):
    ans += A_list[i] * (cum_sum_list[N] - cum_sum_list[i])
    ans = ans % 1000000007
print(ans)
### BUGGY CODE ###

N = int(input())

power = 1
for i in range(1,N+1) :
    power *= i

print(power % 1000000007)


### FIXED CODE ###

N = int(input())

power = 1
for i in range(1,N+1) :
    power = i * (power % 1000000007)

print(power % 1000000007)
### BUGGY CODE ###

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

n = int(raw_input())
print 0
status_0 = raw_input()
check = n / 2
if check % 2 == 1:
    check += 1
if status_0 == "Vacant":
    pass
else:
    while 1:
        print check
        status = raw_input()
        if status == "Vacant":
            break
        elif status == status_0:
            check += check / 2
        else:
            check -= check / 2
            
print ""

### FIXED CODE ###

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

import sys

n = int(raw_input())
print 0
sys.stdout.flush()
status_0 = raw_input()
start = 0
end = n-1
check = end
i = 1
if status_0 == "Vacant":
    pass
else:
    while 1:
        print check
        sys.stdout.flush()
        status = raw_input()
        if status == "Vacant":
            break
        elif status == status_0:
            if check % 2 == 0:
                start = check
            else:
                end = check
        else:
            if check % 2 == 0:
                end = check
            else:
                start = check
        check = start+(end-start)/2

quit()
### BUGGY CODE ###

s = input()
K = int(input())

N = len(s)
words = set()
for i in range(N):
    for j in range(i+1, N+1):
        w = s[i:j]
        words.add(w)

print(sorted(list(words))[K-1])

### FIXED CODE ###

s = input()
K = int(input())

N = len(s)
words = set()
for i in range(N):
    for j in range(i+1, i+K+1):
        w = s[i:j]
        if w not in words:
            words.add(w)

print(sorted(list(words))[K-1])
### BUGGY CODE ###

INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = []
for i in range(N):
    A, B = map(int, input().split())
    AB.append((A, B))
dp = [INF] * (H + 1)
dp[0] = 0
for A, B in AB:
    for j in range(H+1):
        dp[j] = min(dp[j], dp[max(j-A, 0)] + B)
print(dp[H])

### FIXED CODE ###

INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [map(int, input().split()) for i in range(N)]
dp = [INF] * (H + 1)
dp[0] = 0
for A, B in AB:
    for j in range(H+1):
        dp[j] = min(dp[j], dp[max(j-A, 0)] + B)
print(dp[H])
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
save = [0]*n
#Ai + i
for i in range(n):
    save[i] = a[i]+i
#j-Aj
ans = 0
for j in range(n):
    b = j-a[j]
    if(b<0):
        continue
    for i in range(j):
        if(b==save[i]):
            ans+=1

print(ans)

### FIXED CODE ###

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

#Ai + i 
#j-Aj
ans = 0
cnt = [0]*(n+1)
for i in range(n-1):
    j=i+1
    a = mp[i]+i
    if(a<=n):
        cnt[a] += 1 
    b = j-mp[j]
    if(b<0):
        continue
    ans += cnt[b]
    

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

n=int(input())
l=list(map(int,input().split()))
r=[0]*(n-1)
t=[0]*(n)
dr={}
dt={l[0]:[0]}
for i in range(1,n):
  x=i-l[i]
  y=i+l[i]
  if x in dr:
    dr[x].append(i)
  else:
    dr[x]=[i]
  if y in dt:
    dt[y].append(i)
  else:
    dt[y]=[i]
ans=0
for x in dr.keys():
  if x in dt:
    y=dr[x]
    z=dt[x]
    for w in y:
      for ww in z:
        if w>ww:
          ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
r=[0]*(n-1)
t=[0]*(n)
dr={}
dt={l[0]:[0]}
for i in range(1,n):
  x=i-l[i]
  y=i+l[i]
  if x in dr:
    dr[x].append(i)
  else:
    dr[x]=[i]
  if y in dt:
    dt[y].append(i)
  else:
    dt[y]=[i]
ans=0
for x in dr.keys():
  if x>0 and x in dt:
    y=dr[x]
    z=dt[x]
    ans+=len(z)*len(y)
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
ans = 0
nn = 1
mm = 1
for i in range(1, N+1):
    nn *= i
for i in range(1, M+1):
    mm *= i

if N == M:
    ans = ((2*nn*mm)%(10**9+7))

elif abs(N-M) ==1:
    ans = ((nn*mm)%(10**9+7))

print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
ans = 0
nn = 1
mm = 1
for i in range(1, N+1):
    nn = (nn*i)%(10**9+7)
for i in range(1, M+1):
    mm = (mm*i)%(10**9+7)

if N == M:
    ans = ((2*nn*mm)%(10**9+7))

elif abs(N-M) ==1:
    ans = ((nn*mm)%(10**9+7))

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

def main():

    N_machi, K_teleport = map(int, input().split())
    to_teleport = list(map(int, input().split()))

    def find_double_town():
        visited_city = [0]
        first_twice = N_machi
        
        next_city = 0
        
        for i in range(N_machi):
            next_city = to_teleport[next_city] - 1
            visited_city.append(next_city)
            if (len(visited_city) != len(set(visited_city))):
                first_twice = i + 1
                break
        
        return (next_city, first_twice)


    index_city, second_visit = find_double_town()
    if (index_city == 0):
        first_visit = 0
    else:
        next_city = 0        
        for i in range(N_machi):
            next_city = to_teleport[next_city] - 1
            
            if (next_city == index_city):
                first_visit = i + 1
                break

    if (K_teleport >= first_visit):
        mod = (K_teleport - first_visit) % (second_visit - first_visit)
        next_city = index_city
        
    else:
        mod = K_teleport
        next_city = 0

    for i in range(mod):
        next_city = to_teleport[next_city] - 1

    ans = next_city + 1

    print(ans)
    # print(first_visit,second_visit)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():

    N_machi, K_teleport = map(int, input().split())
    to_teleport = list(map(int, input().split()))

    visited_city = [1]
    order = [-1 for i in range(N_machi + 1)]
    order[1] = 0
    next_city = 1
    
    for i in range(N_machi):
        next_city = to_teleport[next_city - 1]
        tmp = order[next_city]
        
        if (tmp == -1):
            visited_city.append(next_city)
            order[next_city] = i + 1
        else:
            break
    
    first = order[next_city]
    len_loop = len(visited_city) - first
    
    if (K_teleport < first):
        ans = visited_city[K_teleport]
    else:
        mod = (K_teleport - first) % len_loop
        ans = visited_city[first + mod]
    
    print(ans)
        

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

import itertools
import math
import sys
from collections import Counter
from fractions import gcd
from functools import reduce
import sys
sys.setrecursionlimit(4100000)

INF = 1 << 60

# ここから書き始める
n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [INF] * n
dp[0] = 0
for i in range(1, n):
    for j in range(i - k, i):
        if j < 0:
            continue
        dp[i] = min(dp[i], dp[j] + abs(h[j] - h[i]))
print(dp[-1])


### FIXED CODE ###

import itertools
import math
import sys
from collections import Counter
from fractions import gcd
from functools import reduce
import sys
sys.setrecursionlimit(4100000)

INF = 1 << 60

# ここから書き始める
n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [INF] * n
dp[0] = 0
for i in range(n):
    for j in range(1, k + 1):
        if i + j == n:
            break
        dp[i + j] = min(dp[i + j], dp[i] + abs(h[i] - h[i + j]))
print(dp[-1])