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

N, K = map(int, input().split())
MOD = 1000000007
checked = [[[False for _ in range(K * 2)] for _ in range(K * 2)] for _ in range(N * 2)]
ans_f = [[[0 for _ in range(K * 2)] for _ in range(K * 2)] for _ in range(N * 2)]

def f(n, k, i):
  if i == 1:
    return n - k + 1
  if checked[n][k][i]:
    return ans_f[n][k][i]
  
  ret = 0
  for j in range(1, k - i + 2):
    for l in range(j + 1, n - k + j + 1):
      tmp =  f(n - l, k - j, i - 1)
      checked[n - l][k - j][i - 1] = True
      ans_f[n - l][k - j][i - 1] = tmp
      ret += tmp
  return ret

for i in range(1, K + 1):
  print(f(N, K, i) % MOD)

### FIXED CODE ###

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

fact = [1]
for i in range(1, N):
  fact.append(fact[-1] * i)

def comb(n, k):
  return (fact[n] // (fact[n - k] * fact[k])) % MOD

def f2(n, k):
  return comb(n + k - 1, k - 1)

def f(n, k):
  if n < k:
    return 0
  if n == 0 and k == 0:
    return 1
  if k < 1:
    return 0
  return f2(n - k, k)

for i in range(1, K + 1):
  blue = f(K, i)
  red = (f(N - K, i - 1) + 2 * f(N - K, i) + f(N - K, i + 1)) % MOD
  ans = blue * red
  print(ans % MOD)
### BUGGY CODE ###

n = int(input())
sticks = list(map(int, input().split()))
multi = set()
f = 0
s = 0
for i in sticks:
  if sticks.count(i) >= 2:
    if i > f:
      f, s = i, f

print(f * s)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
l = []

for i in range(0, N - 1):
    if len(l) == 2:
        break
    if A[i] == A[i + 1] and not A[i] == 0:
        l.append(A[i])
        A[i + 1] = 0
        
if len(l) == 2:
    print(l[0] * l[1])
else:
    print('0')
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def solve(S: str):
    N = len(S)
    dp = [[0 for _ in range(13)] for _ in range(len(S))]
    if S[N-1] != '?':
        dp[0][int(S[N-1])] = 1
    else:
        dp[0] = [1,1,1,1,1,1,1,1,1,1,0,0,0]
    ten = [1]
    for i in range(1, len(S)):
        ten.append(ten[-1] * 10 % 13)
        ii = len(S) - i - 1
        for j in range(13):
            if S[ii] == '?':
                for ll in range(10):
                    kk = ll * ten[i] % 13
                    dp[i][j] += dp[i-1][(13 + j - kk)%13]
                    dp[i][j] %= MOD
            else:
                x = int(S[ii])
                m = x * ten[i] % 13
                dp[i][j] = dp[i-1][(13+j-m)%13]
                dp[i][j] %= MOD
    print(dp[len(S)-1][5])
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def solve(S: str):
    N = len(S)
    dp = [[0 for _ in range(13)] for _ in range(len(S))]
    if S[N-1] != '?':
        dp[0][int(S[N-1])] = 1
    else:
        dp[0] = [1,1,1,1,1,1,1,1,1,1,0,0,0]
    ten = [1]
    for i in range(1, len(S)):
        ten.append(ten[-1] * 10 % 13)
        ii = len(S) - i - 1
        for j in range(13):
            if S[ii] == '?':
                for ll in range(10):
                    kk = ll * ten[i] % 13
                    dp[i][j] += dp[i-1][(13 + j - kk)%13]
                    dp[i][j] %= MOD
            else:
                x = int(S[ii])
                m = x * ten[i] % 13
                dp[i][j] = dp[i-1][(13+j-m)%13]
                dp[i][j] %= MOD
    print(dp[len(S)-1][5])
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

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

import itertools
n = int(input())
#
# lst = []
# for v in itertools.permutations(range(1,n+1),n):
#     tmp = 0
#     for i in range(n):
#         tmp += (i+1) % v[i]
#     lst.append(tmp)
# print(max(lst))
ans = 0
for i in range(1,n):
    ans += i
print(ans)

### FIXED CODE ###

import itertools
n = int(input())
#
# lst = []
# for v in itertools.permutations(range(1,n+1),n):
#     tmp = 0
#     for i in range(n):
#         tmp += (i+1) % v[i]
#     lst.append(tmp)
# print(max(lst))
ans = 0
for i in range(1,n):
    ans += i
print(ans)
### BUGGY CODE ###

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

checked = [0 for _ in range(N)]
nums.sort()
answer = N
for i, num in enumerate(nums):
  if checked[i] == 1:
    continue
  else:
    if i == N-1:
      break
    same = False
    for j in range(i+1, N):
      if nums[j]%num == 0 and checked[j] == 0:
        checked[j] = 1
        answer -= 1
        if nums[j] == num:
          same = True
    if same:
      answer -= 1
print(answer)

### FIXED CODE ###

N = int(input())
nums = list(map(int, input().split()))
nums.sort()
checked = [0 for _ in range(nums[-1]+1)]
answer = 0
for i in range(N-1):
  if checked[nums[i]] == 1:
    continue
  else:
    if nums[i] != nums[i+1]:
      answer += 1
    count = 1
    temp = nums[i]
    while(temp <= nums[-1]):
      checked[temp] = 1
      count += 1
      temp= nums[i]*count
if checked[nums[-1]] == 0:
  answer += 1
print(answer)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
cnt = {}

for i in a:
    if i in cnt.keys():
        cnt[i] += 1
    else:
        cnt[i] = 1

cnt = sorted(cnt.items(), key=lambda x: x[1])

ans, k = 0, len(cnt) - k
for i in range(len(cnt) + 1):
    if 0 >= k:
        print(ans)
        break
    ans += cnt[i][1]
    k -= 1


### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
ball = [0]*n

for i in a:
    ball[i - 1] += 1
ball.sort(reverse=True)

ans = 0
if len(ball) > k:
    for i in range(k):
        ans += ball[i]
    ans = n - ans
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
S = input()
*S, = map(int, list(S))
zeros = []
ones = []
if S[0] == 0:
    ones.append(0)
cnt = 1
now = S[0]
for i in range(1, N):
    if now == S[i]:
        cnt += 1
    else:
        if now == 0:
            zeros.append(cnt)
        else:
            ones.append(cnt)
        cnt = 1
        now = S[i]
if now == 0:
    zeros.append(cnt)
else:
    ones.append(cnt)
if S[-1] == 0:
    ones.append(0)

if len(zeros) <= K:
    print(len(S))
else:
    ans = 0
    for i in range(len(zeros) - K+1):
        aaa = sum(zeros[i:i + K]) + sum(ones[i:i + K])+ones[i+K]
        # if (S[-1] != 0 and i == saigo)or (S[0] != 0 and i == 0):
        #aaa += ones[i+K]
        ans = max(aaa, ans)
    print(ans)


### FIXED CODE ###

from numpy import cumsum
N, K = map(int, input().split())
S = input()
*S, = map(int, list(S))
zeros = [0]
ones = [0]
if S[0] == 0:
    ones.append(0)
cnt = 1
now = S[0]
for i in range(1, N):
    if now == S[i]:
        cnt += 1
    else:
        if now == 0:
            zeros.append(cnt)
        else:
            ones.append(cnt)
        cnt = 1
        now = S[i]
if now == 0:
    zeros.append(cnt)
else:
    ones.append(cnt)
if S[-1] == 0:
    ones.append(0)

c_zero = cumsum(zeros)
c_one = cumsum(ones)
# print(zeros)
# print(c_zero)
# print(c_one)
if len(zeros) <= K:
    print(len(S))
else:
    ans = 0
    for i in range(0, len(zeros) - K):
        #print(i, K)
        #print(c_zero[i+K]-c_zero[i], c_one[i+K+1]-c_one[i])
        aaa = c_zero[i+K]-c_zero[i] + c_one[i+K+1]-c_one[i]
        #aaa = sum(zeros[i:i + K]) + sum(ones[i:i + K])+ones[i+K]
        # if (S[-1] != 0 and i == saigo)or (S[0] != 0 and i == 0):
        #aaa += ones[i+K]
        ans = max(aaa, ans)
    print(ans)
### BUGGY CODE ###

n = int(input())
array = [int(x) for x in input().split()]

tmp_res = 0
tmp_ici = 0
tmp_array = []
for i in array:
    tmp_array.append(abs(tmp_ici-i))
    tmp_ici = i
tmp_array.append(abs(tmp_ici-0))

array = [0] + array + [0]
for i in range(n):
    c = array[i]
    cc = array[i+2]
    a = tmp_array[:i]
    b = tmp_array[i+2:]
    print(sum(a)+abs(c-cc)+sum(b))

### FIXED CODE ###

n = int(input())
array = [int(x) for x in input().split()]

tmp_res = 0
tmp_ici = 0
tmp_array = []
for i in array:
    tmp_array.append(abs(tmp_ici-i))
    tmp_ici = i
tmp_array.append(abs(tmp_ici-0))
tmp_sum = sum(tmp_array)

array = [0] + array + [0]
for i in range(n):
    c = array[i]
    cc = array[i+2]
    a = sum(tmp_array[i:i+2])
    print(tmp_sum-a+abs(c-cc))
### BUGGY CODE ###

N = int(input())
c = input()
ans = []

for i in range(0, N+1):
  p = i  #仕切り
  l = c[:p]
  r = c[p:]
  R = l.count("W")
  W = r.count("R")
  ans.append(max(R,W))

print(min(ans))

### FIXED CODE ###

N = int(input())
c = input()
ans = [-1] * (N+1)

for i in range(0, N+1):
  if i == 0:
    l = c[:i]
    r = c[i:]
    W = l.count("W")
    R = r.count("R")
  else:
    if (c[i-1]) == "W":
      W += 1
    elif (c[i-1]) == "R":
      R -= 1

  ans[i] = max(R, W)
      
print(min(ans))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 0
tmp = []
flag = [0]*N
for i in range(N):
    f = 0
    for j in range(N):
        if i == j:
            continue
        else:
            if A[i]%A[j]==0:
                f=1
                break
    if f == 0:
        ans += 1
    

print(ans)
# print(tmp)
# print(flag)

### FIXED CODE ###

# エラトステネスの篩を使う！O(nloglogn)
N = int(input())
A = list(map(int,input().split()))

listA = [0] * (10**6+10)
ans = 0
for i in A:
    if listA[i] != 0:
            listA[i] = 2
            continue
    for j in range(i,10**6+10,i):
        listA[j] += 1

for i in A:
    if listA[i] == 1:
        ans += 1

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

import math
n=int(input())
for i in range(1,n+1):
  max = int(math.sqrt(i))
  result = 0
  for x in range(1,max+1):
    max = int(math.sqrt(i - x * x))
    for y in range(1,max+1):
      max = int(math.sqrt(i - x * x - y * y))
      for z in range(1,max+1):
        if x * x + y * y + z * z + x * y + y * z + x * z == i:
          result += 1
  print(result)

### FIXED CODE ###

nn=int(input())
nc = [0] * (nn + 1)
for x in range(1, 100):
  for y in range(1, 100):
    for z in range(1, 100):
      a = x * x + y * y + z * z + x * y + x * z + y * z
      if a > nn:
        break
      nc[a] += 1
for i in range(1, nn + 1):
  print(nc[i])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from collections import Counter


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

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

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

    return


def main():

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


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


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

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

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

    return


def main():

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


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

import sys
input = sys.stdin.readline

def unite(node_a, node_b):
    root_a = node_a.root()
    root_b = node_b.root()
    if root_a == root_b:
        return False
    # if root_b.depth > root_a.depth:
    #     root_a, root_b = root_b, root_a
    root_b.is_root = False
    root_b.parent = root_a
    root_a.depth = max(root_a.depth, root_b.depth+1)
    return True

class Node:
    def __init__(self, id):
        self.id = id
        self.is_root = True
        self.parent = None
        self.depth = 1
    
    def root(self):
        if self.is_root:
            return self
        elif self.parent.is_root:
            return self.parent
        else:
            self.parent = self.parent.root()
            return self.parent

def main():
    N, K, L = map(int, input().split())
    
    trains = [Node(i) for i in range(N)]
    streets = [Node(i) for i in range(N)]

    for i in range(K):
        p, q = map(int, input().split())
        p -= 1; q -= 1
        unite(trains[p], trains[q])
    for i in range(L):
        r, s = map(int, input().split())
        r -= 1; s -= 1
        unite(streets[r], streets[s])
    dic = {}
    roots = []
    for i in range(N):
        tmp = (trains[i].root().id, streets[i].root().id)
        roots.append(tmp)
        if tmp in dic:
            dic[tmp] += 1
        else:
            dic[tmp] = 1
    
    for i in range(N-1):
        print(dic[roots[i]], end=" ")
    print(dic[roots[N-1]])

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def unite(node_a, node_b):
    root_a = node_a.root()
    root_b = node_b.root()
    if root_a == root_b:
        return False
    if root_b.depth > root_a.depth:
        root_a, root_b = root_b, root_a
    root_b.is_root = False
    root_b.parent = root_a
    root_a.depth = max(root_a.depth, root_b.depth+1)
    return True

class Node:
    def __init__(self, id):
        self.id = id
        self.is_root = True
        self.parent = None
        self.depth = 1
    
    def root(self):
        if self.is_root:
            return self
        elif self.parent.is_root:
            return self.parent
        else:
            self.parent = self.parent.root()
            return self.parent

def main():
    N, K, L = map(int, input().split())
    
    trains = [Node(i) for i in range(N)]
    streets = [Node(i) for i in range(N)]

    for i in range(K):
        p, q = map(int, input().split())
        p -= 1; q -= 1
        unite(trains[p], trains[q])
    for i in range(L):
        r, s = map(int, input().split())
        r -= 1; s -= 1
        unite(streets[r], streets[s])
    dic = {}
    roots = []
    for i in range(N):
        tmp = (trains[i].root().id, streets[i].root().id)
        roots.append(tmp)
        if tmp in dic:
            dic[tmp] += 1
        else:
            dic[tmp] = 1
    
    for i in range(N-1):
        print(dic[roots[i]], end=" ")
    print(dic[roots[N-1]])

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




n,k = map(int,input().split())
c = [[] for _ in range(n)]

for i in range(n - 1):
	A,B = map(int,input().split())
	
	#c[min(A - 1,B - 1)].append(max(A - 1,B - 1))
	
	c[A - 1].append(B - 1)
	c[B - 1].append(A - 1)

pat = k
pat_arr = [0 for _ in range(n)]
pat_arr[0] = k
queue = [0]

pat = k

for i in range(len(c)):c[i] = set(c[i])

"""
for i in c:print(len(i))


for j in range(len(c[0])):
	pat *= (k-j-1)
	pat %= 1000000007
for i in range(1,len(c)):
	for j in range(len(c[i])):
		pat *= (k-j-2)
		pat %= 1000000007
print(pat)






exit()
"""
while(queue):
	pos = queue.pop(0)
	num = k-2
	if(pos == 0):num += 1
	
	for i in c[pos]:
		if(pat_arr[i] != 0):continue
		queue.append(i)
		pat_arr[i] = num
		pat *= num
		pat %= 1000000007
		num -= 1
		
		
print(pat % 1000000007)

### FIXED CODE ###

n,k = map(int,input().split())
#a = [0 for _ in range(n)]
#b = [0 for _ in range(n)]
c = [[] for _ in range(n)]

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

pat = k
pat_arr = [0 for _ in range(n)]
pat_arr[0] = k
queue = [0]



while(queue):
	pos = queue.pop(0)
	num = k-2
	if(pos == 0):num += 1
	
	for i in c[pos]:
		if(pat_arr[i] != 0):continue
		queue.append(i)
		pat_arr[i] = num
		pat *= num
		pat %= 1000000007
		num -= 1
		
		
print(pat % 1000000007)
### BUGGY CODE ###

L = input()
n = len(L)
ans = 0
mod = 10**9 + 7
for i in range(1,n+1):
    if L[-i] == '1':
        if i == 1:
            ans = 3
        else:
            ans = ans*2 % mod
            ans = (ans + 3**(i-1))%mod
    else:
        if i == 1:
            ans = 1
print(ans)

### FIXED CODE ###

L = input()
n = len(L)
mod = 10**9+7
pow3 = [1]
for i in range(1,n):
    x = (3*pow3[i-1])%mod
    pow3.append(x)
ans = 0
for i in range(1,n+1):
    if L[-i] == '1':
        if i == 1:
            ans = 3
        else:
            ans = ans*2 % mod
            ans = (ans + pow3[i-1])%mod
    else:
        if i == 1:
            ans = 1
print(ans)
### BUGGY CODE ###

def binary_search(list, item):
    low = 0
    lengyh = len(list)
    if lengyh != 0 and list[lengyh - 1] < item:
        return lengyh - 1
    high = lengyh - 1

    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]

        if guess == item - 1 or (mid < lengyh - 1 and (guess < item and list[mid + 1] > item)) or (mid == lengyh - 1 and guess < item):
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1

    return None


N = int(input())
str_l = input()
num = 0
L = []
for v in str_l.split(' '):
    L.append(int(v))

L.sort()
for i in range(N):
    a = L[i]
    for j in range(i, N - 1):
        b = L[j + 1]
        index = binary_search(L[j + 2:], a + b)
        if index is None:
            continue
        else:
            for k in range(0, index + 1):
                c = (L[j + 2:])[k]
                if b + c > a and a + c > b:
                    num += 1

print(num)


### FIXED CODE ###

import bisect


N = int(input())
str_l = input()
num = 0
L = []
for v in str_l.split(' '):
    L.append(int(v))

L.sort()
for i in range(N - 1):
    a = L[i]
    for j in range(i, N - 2):
        b = L[j + 1]
        index = bisect.bisect_left(L[j + 2:], a + b)
        num += index
        # for k in range(0, index):
        #     c = (L[j + 2:])[k]
        #     if b + c > a and a + c > b:
        #         num += 1

print(num)
### BUGGY CODE ###

import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**6)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    N, M = geta(int)
    g = defaultdict(lambda: [])
    for _ in range(M):
        x, y = geta(int)
        g[x].append(y)

    dp = [-1] * (N + 1)

    def dfs(i):
        if dp[i] != -1:
            return dp[i]
        else:
            dist = 0
            for j in g[i]:
                dist_j = 1 + dfs(j)
                if dist_j > dist: dist = dist_j
            return dist

    ans = 0
    for i in range(1, N + 1):
        tmp = dfs(i)
        if tmp > ans: ans = tmp

    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**6)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    N, M = geta(int)
    g = defaultdict(lambda: [])
    for _ in range(M):
        x, y = geta(int)
        g[x].append(y)

    dp = [-1] * (N + 1)

    def dfs(i):
        if dp[i] == -1:
            dist = 0
            for j in g[i]:
                dist_j = 1 + dfs(j)
                if dist_j > dist: dist = dist_j
            dp[i] = dist
        return dp[i]

    ans = 0
    for i in range(1, N + 1):
        tmp = dfs(i)
        if tmp > ans: ans = tmp

    print(ans)


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

n,k,c=map(int, input().split())
s=input()
L=[0]*k
R=[0]*k
m=0
l=0
for i in range(k):
    while s[m]=="x":
        m+=1
    L[i]=m
    m+=c+1
    while s[n-l-1]=="x":
        l+=1
    R[i]=n-l-1
    l+=c+1
for i in range(k):
    if sorted(R)[i]==L[i]:
        print(L[i]+1)

### FIXED CODE ###

n,k,c=map(int, input().split())
s=input()
L=[0]*k
R=[0]*k
m=0
l=0
for i in range(k):
    while s[m]=="x":
        m+=1
    L[i]=m
    m+=c+1
    while s[n-l-1]=="x":
        l+=1
    R[i]=n-l-1
    l+=c+1
for i in range(k):
    if R[k-i-1]==L[i]:
        print(L[i]+1)
### BUGGY CODE ###

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

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


### FIXED CODE ###

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

c1 = {}
c2 = {}

for i in range(N):
    c1.setdefault(i + A[i], 0)
    c1[i + A[i]] += 1
    c2.setdefault(i - A[i], 0)
    c2[i - A[i]] += 1

result = 0
for k in set(c1).intersection(c2):
    result += c1[k] * c2[k]
print(result)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,m= map(int,input().split())

B = []
C = [0]*n
ans = 0
pna = 0
for i in range(m):
    A = list(map(str,input().split()))
    if A[1]=="AC":
        if A[0] not in B :
            B.append(A[0])
            ans += 1
            pna += C[int(A[0])-1]
    if A[1]=="WA"  :
        C[int(A[0])-1] += 1 
print(ans,pna)

### FIXED CODE ###

N,M = [int(x) for x in input().split()]
count = [0]*N
ac = 0
wa = 0
ireta = []
for i in range(M):
    a,b = input().split()
    a = int(a)
    if b == "AC" and count[a-1] == 0:
        count[a-1] = 1
        ac += 1
    elif count[a-1] == 0:
        ireta.append(a)
        wa += 1
for i in range(len(ireta)):
    if count[ireta[i]-1] == 0:
        wa -= 1
print(ac,wa)
### BUGGY CODE ###

n = int(input())
s = input()
c_list = [(0, 0, 0) for i in range(n)]
r = 0
g = 0
b = 0
n_list = [0]*n
p = -1
for i in range(n):
  if s[i] == "R":
    r += 1
    p = 0
  elif s[i] == "G":
    g += 1
    p = 1
  else:
    b += 1
    p = 2
  c_list[i] = (r, g, b)
  n_list[i] = p
count = 0
for i in range(n-2):
  for j in range(i+1, n-1):
    c1 = n_list[i]
    c2 = n_list[j]
    if c1 != c2:
      if j+j-i < n and 3 - n_list[j+j-i] - c1 - c2 == 0:
        count += c_list[n-1][3-c1-c2] - c_list[j][3-c1-c2] -1
      else:
        count += c_list[n-1][3-c1-c2] - c_list[j][3-c1-c2]
print(count)
        
  

### FIXED CODE ###

n = int(input())
s = input()
c_list = [(0, 0, 0) for i in range(n)]
r = 0
g = 0
b = 0
n_list = [0]*n
p = -1
for i in range(n):
  if s[i] == "R":
    r += 1
    p = 0
  elif s[i] == "G":
    g += 1
    p = 1
  else:
    b += 1
    p = 2
  c_list[i] = (r, g, b)
  n_list[i] = p
count = 0
for i in range(n-2):
  for j in range(i+1, n-1):
    c1 = n_list[i]
    c2 = n_list[j]
    if c1 != c2:
      if j+j-i < n and 3 - n_list[j+j-i] - c1 - c2 == 0:
        count += c_list[n-1][3-c1-c2] - c_list[j][3-c1-c2] -1
      else:
        count += c_list[n-1][3-c1-c2] - c_list[j][3-c1-c2]
print(count)
### BUGGY CODE ###

def resolve():
	# N: 足場の個数, K: 1回で右にジャンプできる足場の数
	N, K = map(int, input().split())
	# h: 各足場の高さ
	h = list(map(int, input().split()))
	# dpテーブル宣言: dp[今いる足場の番号-1]=最小コスト
	dp = [float('inf')] * N
	dp[0] = 0

	# k個左の足場からジャンプして来た時の最小コストを調べる
	for n in range(1, N):
		for k in range(min(n, K)):
			dp[n] = min(
				dp[n],
				abs(h[n] - h[n-k-1]) + dp[n-k-1]
			)
	print(dp[N-1])

resolve()

### FIXED CODE ###

def resolve():
	# N: 足場の個数, K: 1回で右にジャンプできる足場の数
	N, K = map(int, input().split())
	# h: 各足場の高さ
	# dpテーブル宣言: dp[今いる足場の番号-1]=[最小コスト, 足場の高さ]
	dp = [
		[float('inf'), int(h_)]
		for h_ in input().split()
	]
	dp[0][0] = 0
	dp[1][0] = abs(dp[0][1] - dp[1][1])

	# k個左の足場からジャンプして来た時の最小コストを調べる
	for n in range(2, N):
		index_0 = max(0, n-K)
		h_ = dp[n][1]
		dp[n][0] = min(
			[
				abs( h_ - dp_[1] ) + dp_[0]
				for dp_ in dp[index_0:n]
			]
		)
	print(dp[N-1][0])

resolve()