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

N,K = map(int,input().split())
HList = list(map(int,input().split()))
dp = [0]*(N)

for i in range(N):
    for k in range(1,K+1):
        if i + k > N-1:
            break
        cost = dp[i]+abs(HList[i]-HList[i+k])
        if dp[i+k] == 0:
            dp[i+k] = cost
        else:
            dp[i+k]= min(dp[i+k],cost)

print(dp[N-1])

### FIXED CODE ###

N,K = map(int,input().split())
INF = 10**12
Data = list(map(int,input().split()))
Data.insert(0,0)
DP = [INF]*(N+1)
DP[1]=0
for i in range(2,N+1):
    for j in range(1,K+1):
        if i-j >= 1:
            diff = abs(Data[i]-Data[i-j])
            DP[i] = min(DP[i],DP[i-j]+diff)
print(DP[N])
### BUGGY CODE ###

from collections import deque
H,W = map(int,input().split())
maze = []
for i in range(H):
    maze.append(input())
q = deque()
saitan = [1000000]*H*W
start = []
sumi= []
for i in range(H):
    for k in range(W):
        if maze[i][k] == '#':
            start.append(i*W+k)

for i in start:
    q.append(i)
    sumi.append(i)
    saitan[i] = 0
#print(start)
def bfs(h,w,q,Sumi,Saitan):
    
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    while len(q)>0:
        j = q.popleft()
        y = int(j/w)
        x = j%w
        #print(saitan)
        for k in range(4):
            my = y + dy[k]
            mx = x + dx[k]
            #print(sx,sy,j,x,y,mx,my)
            if not((0 <=my <= h-1) and (0 <= mx <= w-1)):
                #print('q')
                continue
            if (my*w + mx) in Sumi:
                #print('b')
                continue
            if saitan[(my*w + mx)] <= saitan[y*w + x] + 1:
                #print('c')
                continue
                
            saitan[(my*w + mx)] = saitan[y*w + x] + 1
            q.append(my*w + mx)
            Sumi.append(my*w + mx)
    return max(saitan)

print(bfs(H,W,q,sumi,saitan))
#print(saitan)

### FIXED CODE ###

from collections import deque
H,W = map(int,input().split())
maze = []
for i in range(H):
    maze.append(input())
q = deque()
saitan = [1000000]*H*W
for i in range(H):
    for k in range(W):
        if maze[i][k] == '#':
            q.append(i*W+k)
            saitan[i*W+k] = 0
len_q = len(q)

#print(start)
def bfs(h,w,q,Saitan,len_Q):
    
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    while len(q)>0 and len_Q < h * w:
        j = q.popleft()
        y = int(j/w)
        x = j%w
        #print(saitan)
        for k in range(4):
            my = y + dy[k]
            mx = x + dx[k]
            #print(sx,sy,j,x,y,mx,my)
            if not((0 <=my <= h-1) and (0 <= mx <= w-1)):
                #print('q')
                continue
            if saitan[(my*w + mx)] <= saitan[y*w + x] + 1:
                #print('c')
                continue
                
            saitan[(my*w + mx)] = saitan[y*w + x] + 1
            q.append(my*w + mx)
            len_Q += 1
            #Sumi.append(my*w + mx)
    return max(saitan)

print(bfs(H,W,q,saitan,len_q))
#print(saitan)
### BUGGY CODE ###

n, k = list(map(int, input().split()))
h = list(map(int, input().split()))
for i in range(k):
  h[h.index(max(h))] = 0
print(sum(h))

### FIXED CODE ###

n, k = list(map(int, input().split()))
h = list(map(int, input().split()))
if n <= k:
    print(0)
else:
    h.sort()
    print(sum(h[0:len(h)-k]))
### BUGGY CODE ###

def sf(s,queries):

    is_reversed = 0

    for query in queries:
        addl = []
        addr = []
        if query[0] == '1':
            is_reversed ^= 1
        elif query[0] == '2':
            f = query[1]
            c = query[2]
            if is_reversed == 0 and f == '1' or is_reversed == 1 and f == '2':
                addl.append(c)
            elif is_reversed == 0 and f == '2' or is_reversed == 1 and f == '1':
                addr.append(c)

            s = addl + s + addr

    return ''.join(s) if not is_reversed else ''.join(reversed(s))


if __name__ == '__main__':
    s = list(input())
    q = int(input())
    ql = [input().split() for i in range(q)]
    print(sf(s,ql))


### FIXED CODE ###

from collections import deque

def msf(s,queries):
    queue = deque(s)
    addl = queue.appendleft
    addr = queue.append
    is_reversed = 0

    for query in queries:
        if query[0] == '1':
            is_reversed ^= 1
            addl,addr = addr,addl
        elif query[0] == '2':
            f = query[1]
            c = query[2]
            if f == '1':
                addl(c)
            elif f == '2':
                addr(c)
    return ''.join(queue) if not is_reversed else ''.join(reversed(queue))

if __name__ == '__main__':
    s = list(input())
    q = int(input())
    ql = [input().split() for i in range(q)]
    print(msf(s,ql))
### BUGGY CODE ###

N=input()
N=int(N)
A=[]
for i in range(N):
    b=input()
    b=int(b)
    A.append(b)
for i in range(N):
#    A=a
#    print(A)
    data=A.pop(i)

#    print(lst,i)
    print(max(A))
    A.insert(i,data)


### FIXED CODE ###

N=input()
N=int(N)
A=[]
for i in range(N):
    b=input()
    b=int(b)
    A.append(b)
flag=0
max_value=max(A)
for i in range(N):
    if flag==1:
        print(max_value)
    elif A[i]<max_value:
        print(max_value)
    else:
        data=A.pop(i)
        print(max(A))
        A.insert(i,data)
        if max(A)==max_value:
            flag=1
### BUGGY CODE ###

import functools
import sys

sys.setrecursionlimit(10 ** 9)

input()

arr = list(sorted([(v, idx) for idx, v in enumerate(map(int, input().split()))], reverse=True))


@functools.lru_cache(maxsize=None)
def dp(l, r, idx):
    if idx == len(arr):
        return 0

    left = abs(arr[idx][1] - l) * arr[idx][0] + dp(l + 1, r, idx + 1)
    right = abs(arr[idx][1] - r) * arr[idx][0] + dp(l, r - 1, idx + 1)

    return max(left, right)


print(dp(0, len(arr) - 1, 0))


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 9)

input()

arr = list(sorted([(v, idx) for idx, v in enumerate(map(int, input().split()))], reverse=True))

d = [[-1 for _ in range(len(arr))] for _ in range(len(arr))]


def dp(l, r, idx):
    if idx == len(arr):
        return 0

    if d[l][r] != -1:
        return d[l][r]

    left = abs(arr[idx][1] - l) * arr[idx][0] + dp(l + 1, r, idx + 1)
    right = abs(arr[idx][1] - r) * arr[idx][0] + dp(l, r - 1, idx + 1)

    d[l][r] = max(left, right)
    return max(left, right)


print(dp(0, len(arr) - 1, 0))
### BUGGY CODE ###

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

A_max = max(A)

for i in range(A_max):
  print(A.count(i+1))
for i in range(N-A_max):
  print(0)

### FIXED CODE ###

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

ans = [0] * N

for i in range(len(A)):
  ans[A[i]-1] += 1

for i in range(len(ans)):
  print(ans[i])
### BUGGY CODE ###

s = input()
t = input()
#dp[i][j] => s[i], t[j]までの最長部分文字列


dp = [["" for i in range(len(t) + 1)] for j in range(len(s) + 1)]
for j in range(len(t)):
    for i in range(len(s)):
        if s[i] == t[j]:
            v =  [dp[i][j] + s[i], dp[i + 1][j],dp[i][j + 1]]
            v = sorted(v, key = lambda x:len(x))
            dp[i + 1][j + 1] = v[-1]
        else:
            v =  [ dp[i + 1][j],dp[i][j + 1]]
            v = sorted(v, key = lambda x:len(x))
            dp[i + 1][j + 1] = v[-1]
print(dp[-1][-1])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)
s = input()
t = input()

#dp[i][j] => s[i], t[j]までの最長部分文字列

dp = [[0] * (len(t) + 1) for j in range(len(s) + 1)]
for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        if s[i-1] == t[j-1]:
            x = 1
        else:
            x = 0
        dp[i][j] = max(dp[i-1][j-1] + x, dp[i-1][j], dp[i][j-1])


def make_ans(a, b):
    if a ==  0 or b == 0:
        return 
    if s[a-1] == t[b-1]:
        make_ans(a-1,b-1)
        ans.append(s[a-1])
    else:
        if a == 0:
            make_ans(a, b - 1)
        elif b == 0:
            make_ans(a - 1,b)
        else:
            if dp[a - 1][b] > dp[a][b - 1]:
                make_ans(a-1,b)
            else:
                make_ans(a,b-1)

ans = []
make_ans(len(s),len(t))
print("".join(ans))
### BUGGY CODE ###

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

cnt = [0]*n
for i in range(1, n):
    cnt[i] = min(abs(h[m]-h[i])+cnt[m] for m in range(max(0, i-k), i))
print(cnt[n-1])


### FIXED CODE ###

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

cnt = [0]*n
for i in range(1, n):
    j = max(0,i-k)
    cnt[i] = min(abs(h[m]-h[i])+cnt[m] for m in range(j,i))
print(cnt[n-1])
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 998244353

A, B, C, D = MAP()

dp = [[0]*(D+1) for _ in range(C+1)]
dp[A][B] = 1

for i in range(A, C+1):
    for j in range(B, D+1):
        if j > B:
            dp[i][j] += dp[i][j-1] * i
        if i > A:
            dp[i][j] += dp[i-1][j] * j
        if A < i and B < j:
            dp[i][j] -= (i-1) * (j-1) * dp[i-1][j-1]
        dp[i][j] %= mod

print(dp[C][D])


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 998244353

A, B, C, D = MAP()

dp = [[0]*(D+1) for _ in range(C+1)]
dp[A][B] = 1

for i in range(A, C+1):
    for j in range(B, D+1):
        if j > B:
            dp[i][j] += dp[i][j-1] * i
        if i > A:
            dp[i][j] += dp[i-1][j] * j
        if A < i and B < j:
            dp[i][j] -= (i-1) * (j-1) * dp[i-1][j-1]
        dp[i][j] %= mod

print(dp[C][D])
### BUGGY CODE ###

k=int(input())
curr=7
count=1
if(k%2==0 or k%5==0):
	print(-1)
else:
	for i in range(1,k+1):
		if(curr%k==0):
			print(count)
			break
		else:
			curr=curr*10+7
			count+=1

### FIXED CODE ###

k=int(input())
curr=7
curr=curr%k
count=1
if(k%2==0 or k%5==0):
	print(-1)
else:
	for i in range(1,k+1):
		if(curr==0):
			print(count)
			break
		else:
			curr=(curr*10+7)%k
			count+=1
### BUGGY CODE ###

from math import gcd

def get_sieve_of_eratosthenes_new(n):
    import math
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

prime=get_sieve_of_eratosthenes_new(32000)

def euler_phi(n):
    res=n
    for x in prime:
        if n%x==0:
            res=(res//x)*(x-1)
            while n%x==0:
                n//=x
    if n!=1:
        res=(res//n)*(n-1)
    return res


def biggcd(n,m):
    g=gcd(n,m)
    res=g
    count=2
    while True:
        test=gcd(g**count,m)
        if test>res:
            res=test
            count+=1
        else:
            break
    return res


def solve(a,m,n):
    #print(a,m,n)
    if gcd(a,m)==1:
        if m==1:
            return 1
        phi=euler_phi(m)
        G=gcd(phi,m)
        r0=solve(a,G,n)
        return (((pow(a,n*r0)-n*r0)//G)*pow(n*phi//G,phi-1,m)*phi+r0)%(m*phi//G)
    else:
        big=biggcd(a,m)
        k0=solve(a,m//big,n*big)
        return big*k0

for i in range(int(input())):
    A,M=map(int,input().split())
    print(solve(A,M,1))
    #ans=solve(A,M,1)
    #print(pow(A,ans,M)%M==ans%M)

### FIXED CODE ###

from math import gcd

def get_sieve_of_eratosthenes_new(n):
    import math
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

prime=get_sieve_of_eratosthenes_new(32000)

def euler_phi(n):
    res=n
    for x in prime:
        if n%x==0:
            res=(res//x)*(x-1)
            while n%x==0:
                n//=x
    if n!=1:
        res=(res//n)*(n-1)
    return res


def biggcd(n,m):
    g=gcd(n,m)
    res=g
    count=2
    while True:
        test=gcd(g**count,m)
        if test>res:
            res=test
            count+=1
        else:
            break
    return res


def solve(a,m,n):
    #print(a,m,n)
    if gcd(a,m)==1:
        if m==1:
            return 1
        phi=euler_phi(m)
        G=gcd(phi,m)
        r0=solve(a,G,n)
        mod=m*phi//G
        return ((((pow(a,n*r0,mod)-n*r0)%mod)//G)*pow(n*phi//G,phi-1,m)*phi+r0)%mod
    else:
        big=biggcd(a,m)
        k0=solve(a,m//big,n*big)
        return big*k0

for i in range(int(input())):
    A,M=map(int,input().split())
    print(solve(A,M,1))
    #ans=solve(A,M,1)
    #print(pow(A,ans,M)%M==ans%M)
### BUGGY CODE ###

n, m = map(int, input().split()) 
s = list(map(int, input().split())) 
t = list(map(int, input().split())) 

MOD = 1000000007

dp= [[0] * m for _ in range(n)] 

for i, si in enumerate(s):  
  for j, tj in enumerate(t):
    if i > 0:
      dp[i][j] += dp[i-1][j]
      dp[i][j] %= MOD

    if j > 0:
      dp[i][j] += dp[i][j-1]
      dp[i][j] %= MOD

    if si == tj:
      dp[i][j] += 1
      dp[i][j] %= MOD
    elif i > 0 and j > 0:
      dp[i][j] -= dp[i-1][j-1]
      dp[i][j] %= MOD

print((dp[n-1][m-1] + 1) % MOD)

### FIXED CODE ###

n, m = map(int, input().split()) 
s = list(map(int, input().split())) 
t = list(map(int, input().split())) 

MOD = 1000000007

dp= [[0] * m for _ in range(n)] 

for i, si in enumerate(s):  
  for j, tj in enumerate(t):
    if i > 0:
      dp[i][j] += dp[i-1][j]
      
    if j > 0:
      dp[i][j] += dp[i][j-1]

    if si == tj:
      dp[i][j] += 1
    elif i > 0 and j > 0:
      dp[i][j] -= dp[i-1][j-1]
    
    dp[i][j] %= MOD

print((dp[n-1][m-1] + 1) % MOD)
### BUGGY CODE ###

a,b,x = map(int,input().split())
count=0

for i in range(a,b+1):
    if i%x==0:
        count+=1

print(count)


### FIXED CODE ###

a,b,x = map(int,input().split())

if a == 0:
    print(b // x + 1)
else:
    a -= 1
    print(b // x - a // x)
### BUGGY CODE ###

N, K = map(int,input().split())
A = list(map(int,input().split()))
ans = 1
for i in range(K):
    ans = ans*A[i]
X = []
X.append(ans)
#print(X[0])
for i in range(K, N):
    ans = ans/A[i - K]
    ans = ans*A[i]
    X.append(ans)
    #print(X[i - K + 1])
    if X[i - K] < X[i - K + 1]:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

N, K = map(int,input().split())
A = list(map(int,input().split()))
for i in range(K, N):
    if A[i - K] < A[i]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))


n = inp()
a = inpl()
g = 1
res = 0
for i in a:
    g = i*g//fractions.gcd(i,g)
for i in range(n):
    res += g//a[i]
    res %= mod
print(res)

### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))


n = inp()
a = inpl()
g = 1
res = 0
for i in a:
    g = i*g//fractions.gcd(i,g)
for i in a:
    res += g//i
print(res%mod)
### BUGGY CODE ###

a=int(input())
moji=input()
r=[]
g=[]
b=[]
for i in range(a):
    if moji[i]=="R":
        r.append(i)
    elif moji[i]=="G":
        g.append(i)
    else:
        b.append(i)
res=len(r)*len(g)*len(b)
if len(r)==0 or len(g)==0 or len(b)==0:
    print(0)
else:
    min_len={0:r,1:g,2:b}
    if len(min_len[0])>len(min_len[1]):
        tmp=min_len[0]
        min_len[0]=min_len[1]
        min_len[1]=tmp
    if len(min_len[1])>len(min_len[2]):
        tmp=min_len[1]
        min_len[1]=min_len[2]
        min_len[2]=tmp
    if len(min_len[0])>len(min_len[1]):
        tmp=min_len[0]
        min_len[0]=min_len[1]
        min_len[1]=tmp
    a1=[]
    for i in range(3):
        a1.append(min_len[i])
    
    for i in a1[0]:
        for j in a1[1]:
            if -abs(i-j)+min(i,j) in a1[2]:
                res-=1
            if abs(i-j)+max(i,j) in a1[2]:
                res-=1
            if abs(i-j)%2==0 and  int(abs(i-j)/2)+min(i,j) in a1[2]:
                res-=1
    print(res)

### FIXED CODE ###

a=int(input())
moji=input()
r=[]
g=[]
b=[]
for i in range(a):
    if moji[i]=="R":
        r.append(i)
    elif moji[i]=="G":
        g.append(i)
    else:
        b.append(i)
res=len(r)*len(g)*len(b)
if len(r)==0 or len(g)==0 or len(b)==0:
    print(0)
else:
    for i in range(0,a-2):
      for j in range(i+1,a-1):
        if 2*j-i<a and moji[i]!=moji[j] and moji[j]!=moji[2*j-i] and moji[2*j-i]!=moji[i]:
          res-=1
    print(res)
### BUGGY CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)

h, w = map(int, input().split())
maze = [[-1 for i in range(w)] for j in range(h)]

ans = 0
for i in range(h):
    maze[i] = input()

queue = deque()

left = [[0 for j in range(w)] for i in range(h)]
right = [[0 for j in range(w)] for i in range(h)]
up = [[0 for j in range(w)] for i in range(h)]
down = [[0 for j in range(w)] for i in range(h)]

cnt = 0

for i in range(h):
    cnt = 0
    for j in range(w):
        if maze[i][j] == '#': cnt = 0
        else:
            cnt += 1
            left[i][j] = cnt

    cnt = 0
    for j in reversed(range(w)):
        if maze[i][j] == '#': cnt = 0
        else:
            cnt += 1
            right[i][j] = cnt


for j in range(w):
    cnt = 0
    for i in range(h):
        if maze[i][j] == '#': cnt = 0
        else:
            cnt += 1
            up[i][j] = cnt

    cnt = 0
    for i in reversed(range(h)):
        if maze[i][j] == '#': cnt = 0
        else:
            cnt += 1
            down[i][j] = cnt

ans = 0
for i in range(h):
    for j in range(w):
        tmp = left[i][j] + right[i][j] + up[i][j] + down[i][j] - 3
        ans = max(tmp, ans)

print(ans)


### FIXED CODE ###


from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)

h, w = map(int, input().split())
maze = [[-1 for i in range(w)] for j in range(h)]

ans = 0
for i in range(h):
    maze[i] = input()

queue = deque()

left = [[0 for j in range(w)] for i in range(h)]
right = [[0 for j in range(w)] for i in range(h)]
up = [[0 for j in range(w)] for i in range(h)]
down = [[0 for j in range(w)] for i in range(h)]

cnt = 0

for i in range(h):
    cnt = 0
    for j in range(w):
        if maze[i][j] == '#': cnt = 0
        else:
            cnt += 1
            left[i][j] = cnt

    cnt = 0
    for j in reversed(range(w)):
        if maze[i][j] == '#': cnt = 0
        else:
            cnt += 1
            right[i][j] = cnt


for j in range(w):
    cnt = 0
    for i in range(h):
        if maze[i][j] == '#': cnt = 0
        else:
            cnt += 1
            up[i][j] = cnt

    cnt = 0
    for i in reversed(range(h)):
        if maze[i][j] == '#': cnt = 0
        else:
            cnt += 1
            down[i][j] = cnt

ans = 0
for i in range(h):
    for j in range(w):
        tmp = left[i][j] + right[i][j] + up[i][j] + down[i][j] - 3
        ans = max(tmp, ans)

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

n = int(input())
x = 1
while x % 2 != 0 or x % n != 0:
    x += 1
print(x)

### FIXED CODE ###

n = int(input())

if n % 2 == 0:
    print(n)
else:
    print(n*2)
### BUGGY CODE ###

import sys

#+++++
		
def main():
	n, k = map(int, input().split())
	aal = list(map(int, input().split()))
	
	sss = [0]*(n+1)
	si=0
	for i, a in enumerate(aal):
		si+=a-1
		sss[i+1]=si
	
	count=0
	for j in range(n+1):
		sj=sss[j]
		for i in range(max(0, j-k+1), j):
			si=sss[i]
			if (sj - si) % k == 0:
				pa((i,j))
				count+=1
	
	print(count)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

### FIXED CODE ###

import sys
from collections import defaultdict

#+++++
		
def main():
	n, k = map(int, input().split())
	aal = list(map(int, input().split()))
	
	sss = [0]*(n+1)
	si=0
	for i, a in enumerate(aal):
		si+=a-1
		sss[i+1]=si%k
	
	count=0
	mkl_dict=defaultdict(lambda :0)
	for j in range(n+1):
		sj=sss[j]
		if j-k >= 0:
			mkl_dict[sss[j-k]]-=1
		count += mkl_dict[sj]
		mkl_dict[sj] += 1
			
	print(count)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)