Harryxun/stf_run huggingface dataset:
# N = 4
# ARR = [10, 30, 40, 20]

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

def calculate(n, arr):
    result = aaa(0, n - 1, arr)
    print(result)


def aaa(currentPosition, endPosition, arr, cost=0):
    if currentPosition == endPosition:
        return cost
    if currentPosition == (endPosition - 1):
        return aaa(endPosition, endPosition, arr, cost + abs(arr[endPosition] - arr[currentPosition]))

    a1 = abs(arr[currentPosition + 1] - arr[currentPosition])
    a2 = abs(arr[currentPosition + 2] - arr[currentPosition])

    s1 = aaa(currentPosition + 1, endPosition, arr, cost + a1)
    s2 = aaa(currentPosition + 2, endPosition, arr, cost + a2)
    return min(s1, s2)





calculate(N, ARR)


### FIXED CODE ###

# N = 4
# HRR = [10, 30, 40, 20]
# N = 2
# HRR = [10, 10]

N = int(input())
HRR = list(map(int,input().split()))
result = []
for i in range(N):
    if i == 0:
        result.append(0)
    elif i == 1:
        s1 = result[i - 1] + abs(HRR[i] - HRR[i - 1])
        result.append(s1)
    else:
        s1 = result[i - 1] + abs(HRR[i] - HRR[i - 1])
        s2 = result[i - 2] + abs(HRR[i] - HRR[i - 2])
        result.append(min(s1, s2))

print(result[-1])
import math
n = int(input())
l = []
M= 0
for i in range(n):
    x,y = map(int,input().split())
    l.append((x,y))
for i ,(x1,y1) in enumerate(l):
    for x2,y2 in l[i+1:n]:
        M = max(M,math.sqrt((x1-x2)**2+(y1-y2)**2))
print(M)





### FIXED CODE ###

def a():return input()#s
def ai():return int(input())#a,n or k
def ma():return map(int, input().split())#a,b,c,d or n,k
def ms():return map(str, input().split())#,a,b,c,d
def lma():return list(map(int, input().split()))#x or y
def lms():return list(map(str, input().split()))#x or y
a,b = ma()
c=d=e=-1
for i in range(a+1):
    for j in range(a-i+1):
        if b == i*10000 + j*5000 + (a-i-j)*1000: 
            c,d,e=i,j,a-i-j
            break
print(c,d,e)
import sys
import math

def solve(a, b):
    print(math.gcd(a, b))

if __name__ == '__main__':
    a, b = map(int, sys.stdin.readline().strip().split(" "))
    solve(a, b)

### FIXED CODE ###

import sys
from pprint import pprint
import fractions

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

def solve(a, b):
    print(lcm(a, b))

if __name__ == '__main__':
    a, b = map(int, sys.stdin.readline().strip().split(" "))
    solve(a, b)
a=int(input())

alp=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','z']
if a<27:
 print(alp[a-1])
else:
 b=a//26

 c=a%26
 ans=""
 if b==1:
    ans+='a'
 for i in range(0,17):
  if b/(10**(i))>1:
    d=int(b/(10**(i)))
    ans+=alp[d-1]
  else:
    break
 ans+=alp[c-1]

 print(ans)


### FIXED CODE ###

alp=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
n=int(input())
ans=""
while n>0:
 n-=1
 a=n%26
 ans+=alp[a] 
 n=int(n//26)
 
print(ans[::-1])
str = input().split()
v=""
sa=list()
for i in range(int(str[1])):
    sa.append(input()[:int(str[0])])
sa.sort()
for i in sa:
    v=v+i

print(v)


### FIXED CODE ###

str = input().split()
v=""
sa=list()
for i in range(int(str[0])):
    sa.append(input()[:int(str[1])])
sa.sort()
for i in sa:
    v=v+i

print(v)
def main():
    n, m = get_next_ints()
    ac_count = 0
    wa_count = 0
    
    ac_found = False
    wa = 0
    prev_p = -1
    for i in range(m):
        
        p, result = input().rstrip("\n").split(" ")
        if p != prev_p:
            prev_p = p
            if ac_found:
                ac_count += 1
                wa_count += wa
            ac_found = False
            wa = 0
        if not ac_found:
            if result == 'AC':
                ac_found = True
            else:
                wa += 1
    if ac_found:
        ac_count += 1
        wa_count += wa
    print(ac_count, wa_count)
    
if __name__ == '__main__':
    main()
if __name__ == '__jupyter__':
    import doctest
    print(doctest.testmod())

### FIXED CODE ###

def get_next_ints(delim=" "):
    return tuple([int(float(x)) for x in input().split(delim)])


def get_next_by_types(*value_types, delim=" "):
    return tuple(
        [t(x) for t, x in zip(value_types, input().rstrip("\n").split(delim))])


def main():
    n, m = get_next_ints()
    ac_count = 0
    wa_count = 0

    from collections import defaultdict
    ac_cache = defaultdict(int)
    wa_cache = defaultdict(int)
    ac_count = 0
    wa_count = 0
    wa = 0
    for i in range(m):

        p, result = get_next_by_types(int, str)

        if ac_cache[p] == 0:
            if result == 'AC':

                ac_cache[p] = 1
                ac_count += 1
                wa_count += wa_cache[p]
                wa = 0
            else:
                wa_cache[p] += 1
    print(ac_count, wa_count)


if __name__ == '__main__':
    main()
if __name__ == '__jupyter__':
    import doctest
    print(doctest.testmod())
x = map(int, input().split())
x = x[0], x[2], x[1]
print("Yes" if all(map(lambda x, y: x==y, x, sorted(x))) else "No")


### FIXED CODE ###

import sys
import math
N = list(map(int, input().split()))

t = False
if (N[0] < N[1]) == (N[0] < N[2]):
    if abs(N[1] - N[0]) > abs(N[2] - N[0]):
        t = True

print("Yes" if t else "No")
input();print(eval(input().replace(' ','-1+'))-1)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    a[i] -= 1
print(sum(a))
#!/usr/bin/env python
# -*- coding: utf-8 -*-
N,M,X = map(int,input().split()) #整数の入力
a = list(map(int,input().split()))
#検問所の入力
b=[]
c=[]
for i in range(X+1,N): #X+1からNの範囲の整数について 
  if i in a: #ある整数が検問所の整数として存在する
    b.append(1)
for i in range(1,X): #1からX-1の範囲の整数について
  if i in a: #ある整数が検問所の整数として存在する
    c.append(1)
print(min(sum(b),sum(c))

### FIXED CODE ###

# -*- coding: utf-8 -*-
A,B,X= map(int,input().split())
if A + B >= X and X >= A:
  print("YES")
else:
  print("NO")
n = int(input())
for i in range(n):
	if n[i] == 0:
		break
	print('case ',i+1, ': ', n[i], sep='')

### FIXED CODE ###

### 17.07.2017
n = []
while (True):
	x = int(input())
	if x == 0:
		break
	n.append(int(x))
a = 0
for i in n:
	print('Case ',a+1, ': ', n[a], sep='')
	a += 1
a=map(int, raw_input().split())

if a[0]<a[1]<a[2]:
    print("Yes")
else :
    print("No")

### FIXED CODE ###

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

if a[0]<a[1]<a[2]:
    print("Yes")
else :
    print("No")
s1=input()
s2=input()
if s1[0] == s2[2] and s1[1]==s2[1] and s1[2]==s[1]:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

s1=input()
s2=input()
if s1[0] == s2[2] and s1[1]==s2[1] and s1[2]==s2[0]:
  print("YES")
else:
  print("NO")
a = map(int, raw_input().split())
print a[0]*a[1] 2*a[0]+2*a[1]

### FIXED CODE ###

a = map(int, raw_input().split())
print a[0]*a[1],2*a[0]+2*a[1]
a,b = map(int, raw_input().split());

print "2*(a+b)",
print "a*b"

### FIXED CODE ###

a, b = map(int, raw_input().split())

print a*b, 2*(a+b)
a = list(map(int(),input().split()))
b = list(map(int(),input().split()))
c = list(map(int(),input().split()))
d = [a[0],b[0],c[0]]
e = [a[1],b[1],c[1]]
f = [a[2],b[2],c[2]]
g = [a[0],b[1],c[2]]
h = [a[2],b[1],c[0]]

n = int(input())

bs = []
for _ in int(input(range(n))):
             bs.append(int(input())
       
for l in [a,b,c,d,e,f,g,h]
             if (l[0] in bs) and (l[1] in bs) and (l[2] in bs):
             print("Yes")
             break
else:
             print("No")


### FIXED CODE ###

a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
d = [a[0],b[0],c[0]]
e = [a[1],b[1],c[1]]
f = [a[2],b[2],c[2]]
g = [a[0],b[1],c[2]]
h = [a[2],b[1],c[0]]

n = int(input())

bs = []
for _ in range(n):
    bs.append(int(input()))

for l in [a,b,c,d,e,f,g,h]:
    if (l[0] in bs) and (l[1] in bs) and (l[2] in bs):
        print("Yes")
        break
else:
        print("No")
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    items = [tuple(map(int, input().split())) for _ in range(N)]
    Q = int(input())
    vL = [tuple(map(int, input().split())) for _ in range(Q)]

    H = min(N + 1, 1 << 9)
    Hb = (H - 1).bit_length()
    MX = 10**5
    dp1 = [[0] * (MX + 1) for _ in range(H)]
    for i in range(1, H):
        v, w = items[i - 1]
        for j in range(MX + 1):
            dp1[i][j] = dp1[i >> 1][j]
            if j >= w:
                dp1[i][j] = max(dp1[i][j], dp1[i >> 1][j - w] + v)
    for v, L in vL:
        if v < H:
            print(dp1[v][L])
            continue
        ans = 0
        for i in range(1 << (v.bit_length() - Hb)):
            node = v
            value = weight = 0
            while node >= H:
                if i & 1:
                    value += items[node][0]
                    weight += items[node][1]
                node >>= 1
                i >>= 1
            if weight > L:
                continue
            ans = max(ans, value + dp1[node][L - weight])
        print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
MX = 10**5
def main():
    data = map(int, sys.stdin.buffer.read().split())
    N = next(data)

    H = min(N + 1, 1 << 10)
    dp = [None] * H
    dp[0] = [0] * (MX + 1)
    IV, IW = [], []
    i = 1
    for v, w in zip(data, data):
        if i < H:
            dpi = dp[i >> 1][:]
            dp[i] = dpi
            for j in range(MX, w - 1, -1):
                dpi[j] = max(dpi[j], dpi[j - w] + v)
        else:
            IV.append(v)
            IW.append(w)
        i += 1
        if i > N:
            break

    Q = next(data)
    for v, L in zip(data, data):
        if v < H:
            print(dp[v][L])
            continue

        item_values = []
        item_weights = []
        while v >= H:
            item_values.append(IV[v - H])
            item_weights.append(IW[v - H])
            v >>= 1

        l = len(item_values)
        V = [0] * (1 << l)
        W = [0] * (1 << l)
        ans = dp[v][L]
        for i in range(1, 1 << l):
            msb = i & (-i)
            msbb = msb.bit_length() - 1
            wi = W[i - msb] + item_weights[msbb]
            W[i] = wi
            if wi <= L:
                vi = V[i - msb] + item_values[msbb]
                ans = max(ans, vi + dp[v][L - wi])
                V[i] = vi
        print(ans)

if __name__ == '__main__':
    main()
using namespace std;
#include <iostream>
int main(){
  int N;
  cin >> N;

  if (N % 1000 == 0) cout << 0;
  else cout << 1000 - N % 1000;

  return 0;
}

### FIXED CODE ###

a = int(input())

if a % 1000 == 0:
  out = 0
else:
  out = 1000 - a % 1000

print(out)
n, q = map(int, input().split())
s = "_{}_".format(input())
td = [input().split() for _ in range(q)]

current_l = 0
current_r = n + 1

for t, d in reversed(td):

    if 0 <= current_l + 1 < len(s) and t == s[current_l + 1] and d == "L":
        current_l += 1x

    if 0 <= current_r - 1 < len(s) and t == s[current_r - 1] and d == "R":
        current_r -= 1x

print(max(current_r - current_l - 1, 0))


### FIXED CODE ###

def search_right(a, x, lo=0, hi=None, key=lambda x: x):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x < key(a[mid]): hi = mid
        else: lo = mid+1
    return lo


def search_left(a, x, lo=0, hi=None, key=lambda x: x):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if key(a[mid]) < x: lo = mid+1
        else: hi = mid
    return lo


def get_fin_pos(s, td, golem_pos):
    for t, d in td:
        if 0 <= golem_pos < len(s) and s[golem_pos] == t:
            golem_pos += 1 if d == "R" else -1
    return golem_pos


n, q = map(int, input().split())
s = "_{}_".format(input())
spells = [input().split() for _ in range(q)]

left = search_right(range(len(s)), 0, key=lambda golem: get_fin_pos(s, spells, golem))
right = search_left(range(len(s)), len(s) - 1, key=lambda golem: get_fin_pos(s, spells, golem))

print(right - left)
import sys
sys.setrecursionlimit(10000)
N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(M):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)

def dp(v,dpv,e):
    if dpv[v] != -1:
        return dpv[v]
    if len(e[v])==0:
        dpv[v]=0
        return 0
    res = 0
    for w in e[v]:
        res = max(dp(w,dpv,e),res)
    res += 1
    dpv[v] = res
    return res

def solve(edge):
    dpv = [-1]*N
    for i in range(N):
        dp(i,dpv,edge)
    ans = max(dpv)
    # print(dpv)
    return ans
print(solve(edge))

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(M):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)

def dp(v,dpv,e):
    if dpv[v] != -1:
        return dpv[v]
    if len(e[v])==0:
        dpv[v]=0
        return 0
    res = 0
    for w in e[v]:
        res = max(dp(w,dpv,e),res)
    res += 1
    dpv[v] = res
    return res

def solve(edge):
    dpv = [-1]*N
    for i in range(N):
        dp(i,dpv,edge)
    ans = max(dpv)
    # print(dpv)
    return ans
print(solve(edge))
a,b=[int(x) for x in input().split()]
if a > b :
 print('a>b')
if a == b :
 print('a==b')
if a < b:
 print('a < b')


### FIXED CODE ###

a,b=[int(x) for x in input().split()]
if a > b:
 print('a > b')
elif a == b:
 print('a == b')
else:
 print('a < b')
# coding: utf-8
import sys


def solve(a, begin, end, queue):
    #print(begin, end)
    if begin >= end:
        return
    if end - begin == 1:
        return
    maxx = sorted(list(map(abs, a[begin:end + 1])), reverse=True)[0]
    if maxx in a:
        m = a.index(maxx)
    else:
        m = a.index(-1 * maxx)
        maxx = -1 * maxx
    if maxx == 0:
        return []
    if maxx > 0:
        solve(a, begin, m - 1, queue)
        for i in range(max(0, m - 1), end):
            if a[i + 1] >= a[i]:
                continue
            else:
                a[i + 1] += a[i]
                queue.append((i, i + 1))
                if a[i + 1] < a[i]:
                    a[i + 1] += a[i]
                    queue.append((i, i + 1))
        return queue
    if maxx < 0:
        solve(a, m + 1, end, queue)
        for i in reversed(range(begin, min(len(a) - 1, m + 1))):
            if a[i] <= a[i + 1]:
                continue
            else:
                a[i] += a[i + 1]
                queue.append((i + 1, i))
                if a[i] > a[i + 1]:
                    a[i] += a[i + 1]
                    queue.append((i + 1, i))
        return queue


if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    queue = solve(a, 0, len(a) - 1, [])
    print(len(queue))
    for i in range(len(queue)):
        print(queue[i][0] + 1, queue[i][1] + 1)
    for i in range(len(a)):
        print(i, a[i])


### FIXED CODE ###

# coding: utf-8
import sys


def solve(a, begin, end, queue, cnt):
    #print(begin, end)
    if begin >= end:
        return
    maxx = sorted(list(map(abs, a[begin:end + 1])), reverse=True)[0]
    # print(maxx)
    if maxx in a[begin:end + 1]:
        m = a[begin:end + 1].index(maxx) + begin
    else:
        m = a[begin:end + 1].index(-1 * maxx) + begin
        maxx = -1 * maxx
    #print(m, maxx)
    if maxx == 0:
        return []
    if maxx > 0:
        solve(a, begin, m - 1, queue, cnt + 1)
        for i in range(max(0, m - 1), end):
            if a[i + 1] >= a[i]:
                continue
            else:
                a[i + 1] += a[i]
                queue.append((i, i + 1))
                if a[i + 1] < a[i]:
                    a[i + 1] += a[i]
                    queue.append((i, i + 1))
        return queue
    if maxx < 0:
        solve(a, m + 1, end, queue, cnt + 1)
        for i in reversed(range(begin, min(len(a) - 1, m + 1))):
            if a[i] <= a[i + 1]:
                continue
            else:
                a[i] += a[i + 1]
                queue.append((i + 1, i))
                if a[i] > a[i + 1]:
                    a[i] += a[i + 1]
                    queue.append((i + 1, i))
        return queue


if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    queue = solve(a, 0, len(a) - 1, [], 0)
    print(len(queue))
    for i in range(len(queue)):
        print(queue[i][0] + 1, queue[i][1] + 1)
N,M = map(int,input().split())
L,R = list(map(int,input().split()))
count = 0
for i in range(N+1):
  if i > max(L) and i < min(R):
    count += 1

### FIXED CODE ###

N,M = map(int,input().split())
L = []
R = []
ans = 0
for _ in range(M):
  l, r = map(int, input().split())
  L.append(l)
  R.append(r)
ans = max(0,min(R) - max(L) + 1)
print(ans)
n = list(input())
s_L = list(map(int,input().split())

s_L = sorted(s_L,reverse=True)
if s_L[0] < sum(s_L[1:]):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

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

s_L = list(sorted(s_L,reverse=True))
if s_L[0] < sum(s_L[1:]):
    print("Yes")
else:
    print("No")
a, b = map(int, input().split())

if a > b
    print('a > b')
elif a < b
    print('a < b')
else
    print('a == b')

### FIXED CODE ###

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

if a == b:
    print("a == b")

elif a > b:
    print("a > b")

else:
    print("a < b")
print(int(input()%1000)

### FIXED CODE ###

n = int(input()) % 1000
if n == 0:
    print(0)
else:
    print(1000-n)
N = int(input())
P = list(map(int,input().split()))
count = 0
for i in range(N):
    if P[i] == i+1:
        P[i],P[i+1]=P[i+1],P[i]
        count += 1
print(count)

### FIXED CODE ###

N = int(input())
P = list(map(int,input().split()))
count = 0
for i in range(N):
    if i != N-1 and P[i] == i+1:
        P[i],P[i+1]=P[i+1],P[i]
        count += 1
if P[N-1] == N:
    count += 1
print(count)
n=int(input())
d=sorted(list(map(int,input().split())))


print(int(d[n//2+1]-d[n//2-1]))

### FIXED CODE ###

n = int(input())
d = sorted(list(map(int,input().split())))

print(d[n//2]-d[n//2-1])
import read_val
import copy


def main():
    t = input()
    if t == "1":
        print(1)
        exit(0)
    li = [int(v) for v in input().split(' ')]
    s_li = sorted(li)
    count = 0
    for v in range(s_li[0] - 1, s_li[-1] + 1):
        t_c = 0
        for vv in s_li:
            if v == vv or v - 1 == vv or v + 1 == vv:
                t_c += 1
            if vv > v + 2:
                break
        if t_c > count:
            count = t_c

    print(count)



if __name__ == '__main__':
    main()


### FIXED CODE ###

n = int(input())
cnt = [0] * 100002
a = list(map(int, input().split()))
for v in a:
    cnt[v] += 1
    cnt[v+1] += 1
    cnt[v+2] += 1
    
print(max(cnt))
h, w=map(int, input().split())
s=[list(input()) for _ in range(h)]

def hantei(count,k,l):
    if s[k][l]=="#":
        count+=1
    return count

for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            count=0
            if i ==0:
                if j==0:
                    for k,l in zip([i,i+1,i+1],[j+1,j,j+1]):
                        count=hantei(count,k,l)
                elif j==w-1:
                    for k,l in zip([i,i+1,i+1],[j-1,j-1,j]):
                        count=hantei(count,k,l)
                else:
                    for k,l in zip([i,i,i+1,i+1,i+1],[j-1,j+1,j-1,j,j+1]):
                        count=hantei(count,k,l)

            elif i==h-1:
                if j==0:
                    for k,l in zip([i-1,i-1,i],[j,j+1,j+1]):
                        count=hantei(count,k,l)
                elif j==w-1:
                    for k,l in zip([i,i-1,i-1],[j-1,j-1,j]):
                        count=hantei(count,k,l)
                else:
                    for k,l in zip([i,i,i-1,i-1,i-1],[j-1,j+1,j-1,j,j+1]):
                        count=hantei(count,k,l)

            elif j==0:
                for k,l in zip([i-1,i-1,i,i+1,i+1],[j,j+1,j+1,j,j+1]):
                        count=hantei(count,k,l)
            elif j==w-1:
                for k,l in zip([i-1,i-1,i,i+1,i+1],[j-1,j,j-1,j-1,j]):
                        count=hantei(count,k,l)
            else:
                for k,l in zip([i-1,i-1,i-1,i,i,i+1,i+1,i+1],[j-1,j,j+1,j-1,j+1,j-1,j,j+1]):
                            count=hantei(count,k,l)

            s[i][j]=str(count)

for i in range(h):
    ss=""
    for j in range(w):
        ss+=s[i][j]
    print(ss)
    

### FIXED CODE ###

H, W = map(int, input().split())

INPUT = [list(input()) for i in range(H)]
OUTPUT = INPUT.copy()

for i in range(H):
    for j in range(W):
        if INPUT[i][j] == '#':
            OUTPUT[i][j] = '#'
            continue
        else:
            OUTPUT[i][j] = 0
            for I in (i-1, i, i+1):
                if (I < 0 or H <= I):
                    continue
                for J in (j-1, j, j+1):
                    if (J < 0 or W <= J):
                        continue
                    if INPUT[I][J] == '#':
                        OUTPUT[i][j] += 1


for i in range(H):
    print(''.join(map(str, OUTPUT[i])))
def read():
    N, K = list(map(int, input().strip().split()))
    A = list(map(int, input().strip().split()))
    return N, K, A

def solve(N, K, A):
    S = [0 for _ in range(N+1)]
    for i in range(N):
        S[i+1] = S[i] + A[i]
    
    count_sum = 0
    count = dict()
    for j in range(1, N+1):
        j_mod_k = (S[j] - j) % K  # 0 <= jmodk < K
        if j == 1:
            for i in range(max(0, j-K+1), j):
                # (S[i] - i) % K の値 i_mod_k は、次のループでもほぼ重複する
                # i = max(0, j-K+1) の時の i_mod_k は、i+1で破棄する
                # i = j の時の i_mod_k は、i+1で生成する
                i_mod_k = (S[i] - i) % K
                if i_mod_k in count:
                    count[i_mod_k] += 1
                else:
                    count[i_mod_k] = 1
        else:
            if max(0, j-K+1) != max(0, (j-1)-K+1):
                i = max(0, (j-1)-K+1)
                i_mod_k = (S[i] - i) % K
                if count[i_mod_k] == 1:
                    count.pop(i_mod_k)
                elif count[i_mod_k] > 1:
                    count[i_mod_k] -= 1
            i = j-1
            i_mod_k = (S[i] - i) % K
            if i_mod_k in count:
                count[i_mod_k] += 1
            else:
                count[i_mod_k] = 1
        count_sum += count[j_mod_k] if j_mod_k in count else 0
    return count_sum

if __name__ == '__main__':
    inputs = read()
    print('%d' % solve(*inputs))


### FIXED CODE ###

def read():
    N, K = list(map(int, input().strip().split()))
    A = list(map(int, input().strip().split()))
    return N, K, A

def solve(N, K, A):
    if K == 1:
        return 0
    
    S = [0 for _ in range(N+1)]
    for i in range(N):
        S[i+1] = S[i] + A[i]
    
    count_sum = 0
    count = dict()
    for j in range(1, N+1):
        j_mod_k = (S[j] - j) % K  # 0 <= jmodk < K
        if j == 1:
            for i in range(max(0, j-K+1), j):
                # (S[i] - i) % K の値 i_mod_k は、次のループでもほぼ重複する
                # i = max(0, j-K+1) の時の i_mod_k は、i+1で破棄する
                # i = j の時の i_mod_k は、i+1で生成する
                i_mod_k = (S[i] - i) % K
                if i_mod_k in count:
                    count[i_mod_k] += 1
                else:
                    count[i_mod_k] = 1
        else:
            if max(0, j-K+1) != max(0, (j-1)-K+1):
                i = max(0, (j-1)-K+1)
                i_mod_k = (S[i] - i) % K
                if i_mod_k in count:
                    if count[i_mod_k] == 1:
                        count.pop(i_mod_k)
                    else:
                        count[i_mod_k] -= 1
            i = j-1
            i_mod_k = (S[i] - i) % K
            if i_mod_k in count:
                count[i_mod_k] += 1
            else:
                count[i_mod_k] = 1
        if j_mod_k in count:
            count_sum += count[j_mod_k]
    return count_sum

if __name__ == '__main__':
    inputs = read()
    print('%d' % solve(*inputs))
S, T = map(input().split())
A, B = map(int, input().split())
U = input()

print("A-1 B" if U == S else "A B-1")


### FIXED CODE ###

S, T = input().split()
A, B = map(int, input().split())
U = input()

print(A-1, B) if U == S else print(A, B-1)