AtCoder Beginner Contest 146 - Rem of Sum is Num

Given are a sequence of N positive integers A_1, A_2, \ldots, A_N, and a positive integer K.
Find the number of non-empty contiguous subsequences in A such that the remainder when dividing the sum of its elements by K is equal to the number of its elements. We consider two subsequences different if they are taken from different positions, even if they are equal sequences.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq N \leq 2\times 10^5
 - 1 \leq K \leq 10^9
 - 1 \leq A_i \leq 10^9

-----Input-----
Input is given from Standard Input in the following format:
N K
A_1 A_2 \cdots A_N

-----Output-----
Print the number of subsequences that satisfy the condition.

-----Sample Input-----
5 4
1 4 2 3 5

-----Sample Output-----
4

Four sequences satisfy the condition: (1), (4,2), (1,4,2), and (5).

Source: atcoder | Difficulty: MEDIUM


Solutions:
import sys
from collections import defaultdict
from itertools import accumulate
read = sys.stdin.read
(N, K, *A) = map(int, read().split())
a = list(accumulate([0] + A))
a = [(a[i] - i) % K for i in range(N + 1)]
answer = 0
dic = defaultdict(int)
for (i, x) in enumerate(a):
	answer += dic[x]
	dic[x] += 1
	if i >= K - 1:
		dic[a[i - K + 1]] -= 1
print(answer)


from collections import defaultdict
from itertools import accumulate
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
s = list(accumulate([0] + a))
b = [(s[i] - i) % k for i in range(n + 1)]
d = defaultdict(int)
for i in range(min(k - 1, n + 1)):
	d[b[i]] += 1
ans = 0
for i in range(n):
	d[b[i]] -= 1
	if i + k - 1 <= n:
		d[b[i + k - 1]] += 1
	ans += d[b[i]]
print(ans)


from itertools import accumulate
from collections import defaultdict
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
S = [0] + list(accumulate(A))
S = [s % K for s in S]
ans = 0
counter = defaultdict(int)
queue = []
for (i, s) in enumerate(S):
	t = (s - i) % K
	ans += counter[t]
	counter[t] += 1
	queue.append(t)
	if len(queue) >= K:
		counter[queue[0]] -= 1
		queue.pop(0)
print(ans)


from collections import defaultdict
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
cum = [0] * (N + 1)
for i in range(1, N + 1):
	cum[i] = cum[i - 1] + A[i - 1]
ans = 0
dic = defaultdict(int)
v_by_indx = defaultdict(int)
for i in range(N + 1):
	if i - K >= 0:
		dic[v_by_indx[i - K]] -= 1
	diff = (cum[i] - i) % K
	ans += dic[diff]
	dic[diff] += 1
	v_by_indx[i] = diff
print(ans)


(n, k) = map(int, input().split())
a = list(map(lambda x: (int(x) - 1) % k, input().split()))
s = [0]
for i in a:
	s.append((s[-1] + i) % k)
mp = {}
ans = 0
for i in range(len(s)):
	if i - k >= 0:
		mp[s[i - k]] -= 1
	if s[i] in mp:
		ans += mp[s[i]]
	if s[i] in mp:
		mp[s[i]] += 1
	else:
		mp[s[i]] = 1
print(ans)


from collections import deque
from collections import defaultdict

def p_e():
	(n, k) = map(int, input().split())
	a = [0] + list(map(int, input().split()))
	for i in range(n):
		a[i + 1] = (a[i + 1] + a[i] - 1) % k
	d = defaultdict(int)
	d[0] = 1
	q = deque()
	ans = 0
	for i in range(1, n + 1):
		if i - k >= 0:
			d[a[i - k]] -= 1
		ans += d[a[i]]
		d[a[i]] += 1
	print(ans)
p_e()


from collections import defaultdict
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
a = [0]
for i in A:
	a.append((a[-1] + i - 1) % K)
d = defaultdict(int)
ans = 0
for i in range(N + 1):
	if i >= K:
		d[a[i - K]] -= 1
	ans += d[a[i]]
	d[a[i]] += 1
print(ans)


import sys

def main():
	input = sys.stdin.readline
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	accum = [0] * n
	accum[0] = a[0]
	d = dict()
	ans = 0
	for i in range(1, n):
		accum[i] += a[i] + accum[i - 1]
	accum = [0] + accum
	for j in range(n + 1):
		if j - k >= 0:
			d[(accum[j - k] - (j - k)) % k] -= 1
		if (accum[j] - j) % k not in d:
			d[(accum[j] - j) % k] = 1
		else:
			ans += d[(accum[j] - j) % k]
			d[(accum[j] - j) % k] += 1
	return print(ans)

def __starting_point():
	main()
__starting_point()


(N, K) = map(int, input().split())
A = list(map(int, input().split()))
B = [a % K for a in A]
cs = [0]
for b in B:
	c = (cs[-1] + b - 1) % K
	cs.append(c)
from collections import deque
from collections import defaultdict
qs = defaultdict(lambda : deque())
ans = 0
for (i, c) in enumerate(cs):
	while qs[c] and qs[c][0] + K <= i:
		qs[c].popleft()
	ans += len(qs[c])
	qs[c].append(i)
print(ans)


from collections import defaultdict

def main():
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	X = [0] * (N + 1)
	for (i, a) in enumerate(A):
		X[i + 1] = (X[i] + a - 1) % K
	cnt = defaultdict(int)
	ans = 0
	for i in range(N + 1):
		if i >= K:
			cnt[X[i - K]] -= 1
		ans += cnt[X[i]]
		cnt[X[i]] += 1
	print(ans)
main()


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
r = 0
s = {0: [0]}
for i in range(n):
	r = (r + a[i] - 1) % k
	if r in s:
		s[r].append(i + 1)
	else:
		s[r] = [i + 1]
ret = 0
for key in s:
	a = s[key]
	en = 0
	for st in range(len(a)):
		while en < len(a) and a[en] - a[st] < k:
			en += 1
		ret += en - st - 1
print(ret)


from itertools import accumulate
(n, k) = map(int, input().split())
A = list(map(int, input().split()))
S = [0] + list(accumulate(A))
R = [(S[i] - i) % k for i in range(n + 1)]
r_dict = {}
ans = 0
for i in range(n + 1):
	if R[i] in r_dict:
		ans += r_dict[R[i]]
		r_dict[R[i]] += 1
	else:
		r_dict[R[i]] = 1
	if i - k + 1 >= 0:
		r_dict[R[i - k + 1]] -= 1
print(ans)


from itertools import accumulate
from collections import Counter
(N, K, *A) = map(int, open(0).read().split())
S = [0] + [a % K for a in accumulate((a - 1 for a in A))]
C = Counter()
ans = 0
for (i, s) in enumerate(S):
	ans += C[s]
	C[s] += 1
	if i - K + 1 >= 0:
		C[S[i - K + 1]] -= 1
print(ans)


from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float('inf')
(YES, Yes, yes, NO, No, no) = ('YES', 'Yes', 'yes', 'NO', 'No', 'no')
(dy4, dx4) = ([0, 1, 0, -1], [1, 0, -1, 0])
(dy8, dx8) = ([0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1])

def inside(y, x, H, W):
	return 0 <= y < H and 0 <= x < W

def ceil(a, b):
	return (a + b - 1) // b

def sum_of_arithmetic_progression(s, d, n):
	return n * (2 * s + (n - 1) * d) // 2

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	g = gcd(a, b)
	return a / g * b

def solve():
	(N, K) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	if K == 1:
		print(0)
		return
	dp = [0]
	for i in range(N):
		dp.append(dp[-1] + (A[i] - 1))
	dp = [d % K for d in dp]
	ans = 0
	d = defaultdict(int)
	d[0] = 1
	for i in range(1, N + 1):
		ans += d[dp[i]]
		d[dp[i]] += 1
		if i - K + 1 >= 0:
			d[dp[i - K + 1]] -= 1
	print(ans)

def main():
	solve()

def __starting_point():
	main()
__starting_point()


from collections import defaultdict

def main():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	acca = [0]
	for _a in a:
		acca.append(acca[-1] + _a)
	ans = 0
	cnt = defaultdict(lambda : 0)
	for (i, ac) in enumerate(acca):
		ans += cnt[(ac - i) % k]
		cnt[(ac - i) % k] += 1
		if i >= k - 1:
			cnt[(acca[i - k + 1] - (i - k + 1)) % k] -= 1
	print(ans)
main()


import sys
input = sys.stdin.buffer.readline
from collections import defaultdict

def main():
	(N, K) = map(int, input().split())
	a = list(map(int, input().split()))
	d = defaultdict(int)
	cum = [0]
	for i in range(N):
		cum.append((cum[-1] + a[i] - 1) % K)
	ans = 0
	for i in range(N + 1):
		ans += d[cum[i]]
		d[cum[i]] += 1
		if i >= K - 1:
			d[cum[i - K + 1]] -= 1
	print(ans)
main()


(N, K) = map(int, input().split())
A = list(map(int, input().split()))
DP = dict()
if K == 1:
	print(0)
	exit()
DP[0] = 1
P = 0
Y = [0] * (N + 1)
for i in range(N):
	Y[i + 1] = (Y[i] + A[i] - 1) % K
	P += DP.get(Y[i + 1], 0)
	DP[Y[i + 1]] = DP.get(Y[i + 1], 0) + 1
	if i >= K - 2:
		DP[Y[i - K + 2]] -= 1
print(P)


def shaku(K, lists):
	ans = 0
	SUMS = 0
	index = 0
	for l in range(len(lists)):
		while index < l or (index < len(lists) and SUMS + lists[index] < K):
			SUMS += lists[index]
			index += 1
		ans += index - l
		SUMS -= lists[l]
	return ans
(n, k) = map(int, input().split())
lists = list(map(int, input().split()))
uselist = [0 for i in range(n + 1)]
for i in range(n):
	uselist[i + 1] = uselist[i] + lists[i]
anslist = [0 for i in range(n + 1)]
for j in range(1, n + 1):
	anslist[j] = (uselist[j] - j) % k
dic = {}
for i in range(n + 1):
	if anslist[i] in dic.keys():
		dic[anslist[i]].append(i + 1)
	else:
		dic[anslist[i]] = [1 + i]
answer = 0
for lis in dic.values():
	sublis = [lis[0]]
	for a in range(1, len(lis)):
		sublis.append(lis[a] - lis[a - 1])
	P = shaku(k, sublis)
	for some in lis:
		if some < k:
			answer -= 1
	answer += P
print(answer)


def main():
	from collections import defaultdict, deque
	(N, K) = list(map(int, input().split()))
	a = list(map(int, input().split()))

	def accumulate(a, mod):
		s = 0
		yield s
		for x in a:
			s = (s + x - 1) % mod
			yield s
	(*acc,) = accumulate(a, mod=K)
	d = defaultdict(int)
	dq = deque()
	ans = 0
	for x in acc:
		ans += d[x]
		d[x] += 1
		dq.append(x)
		if len(dq) >= K:
			r = dq.popleft()
			d[r] -= 1
	print(ans)

def __starting_point():
	main()
__starting_point()


(n, k, *a) = map(int, open(0).read().split())
b = [0] * -~n
for i in range(n):
	b[i + 1] = (a[i] + b[i] - 1) % k
d = {k: 0}
a = 0
for (l, r) in zip([k] * min(k, n + 1) + b, b):
	d[l] -= 1
	t = d.get(r, 0)
	a += t
	d[r] = t + 1
print(a)


import sys
(n, k) = map(int, input().split())
a = [int(x) for x in input().split()]
values = dict()
valuelist = [0] * (n + 1)
values[0] = 1
s = 0
ans = 0
if k == 1:
	print(0)
	return
for i in range(n):
	s += a[i] - 1
	s %= k
	if s in values:
		ans += values[s]
		values[s] += 1
	else:
		values[s] = 1
	valuelist[i + 1] = s
	if i >= k - 2:
		values[valuelist[i - k + 2]] -= 1
print(ans)


import itertools, collections
(N, K) = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
C = list(itertools.accumulate([0] + A))
D = [(v - i) % K for (i, v) in enumerate(C)]
dp = collections.Counter(D[:K])
ans = 0
for i in range(N):
	dp[D[i]] -= 1
	ans += dp[D[i]]
	if i + K < len(D):
		dp[D[i + K]] += 1
print(ans)


from collections import Counter
(N, K) = map(int, input().split())
As = list(map(int, input().split()))
Ss = [0]
S = 0
for A in As:
	S += A - 1
	S %= K
	Ss.append(S)
ans = 0
cnt = Counter()
for i in range(N + 1):
	ans += cnt[Ss[i]]
	cnt[Ss[i]] += 1
	if i >= K - 1:
		cnt[Ss[i - K + 1]] -= 1
print(ans)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools
import time, random
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
mod2 = 998244353
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def pe(s):
	return print(str(s), file=sys.stderr)

def JA(a, sep):
	return sep.join(map(str, a))

def JAA(a, s, t):
	return s.join((t.join(map(str, b)) for b in a))

def main():
	(n, k) = LI()
	aa = LI()
	c = collections.defaultdict(int)
	c[0] = 1
	t = [0]
	r = 0
	for i in range(n):
		a = aa[i]
		tt = (t[-1] + a - 1) % k
		t.append(tt)
		if i >= k - 1:
			c[t[i - k + 1]] -= 1
		r += c[tt]
		c[tt] += 1
	return r
print(main())


(n, k) = [int(j) for j in input().split()]
a = [int(j) for j in input().split()]
from itertools import accumulate
l = [0] + list(accumulate(a))
ll = []
for i in range(n + 1):
	ll.append((i - l[i]) % k)
import collections
c = collections.Counter()
ans = 0
for i in range(n + 1):
	ans += c[ll[i]]
	c[ll[i]] += 1
	if i >= k - 1:
		c[ll[i - k + 1]] -= 1
print(ans)


(N, K) = map(int, input().split())
L = list(map(int, input().split()))
R = list()
if K >= N:
	sums = 0
	c = dict()
	for i in range(N):
		sums += L[i]
		sums %= K
		a = (sums - i - 1) % K
		if a in c:
			c[a] += 1
		else:
			c[a] = 1
	ans = 0
	for i in c:
		ans += (c[i] - 1) * c[i] // 2
	if 0 in c:
		print(ans + c[0])
	else:
		print(ans)
else:
	ans = 0
	c = [0] * K
	sums = 0
	for i in range(N):
		sums += L[i]
		sums %= K
		a = (sums - i - 1) % K
		R.append(a)
	for i in range(K - 1):
		c[R[i]] += 1
	ans += c[0]
	c[R[K - 1]] += 1
	for i in range(N):
		if i < N - K:
			ans += c[R[i]] - 1
			c[R[i]] -= 1
			c[R[i + K]] += 1
		else:
			ans += c[R[i]] - 1
			c[R[i]] -= 1
	print(ans)


from collections import defaultdict
(n, k) = map(int, input().split())
a = list(map(lambda x: int(x) - 1, input().split()))
s = [0] * (n + 1)
for i in range(n):
	s[i + 1] = (s[i] + a[i]) % k
mp = defaultdict(int)
ans = 0
for i in range(n + 1):
	ans += mp[s[i]]
	mp[s[i]] += 1
	if i >= k - 1:
		mp[s[i - k + 1]] -= 1
print(ans)


from collections import Counter, deque
(N, K) = list(map(int, input().split()))
A = list(map(int, input().split()))
INF = 10 ** 18
cnt = Counter()
cnt[0] = 1
que = deque([0])
sumR = 0
ans = 0
for (right, a) in enumerate(A, start=1):
	if len(que) >= K:
		cnt[que.popleft()] -= 1
	sumR = (a + sumR) % K
	D = (sumR - right) % K
	ans += cnt[D]
	cnt[D] += 1
	que.append(D)
print(ans)


from collections import defaultdict
import bisect
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
S = [0] * N
for i in range(N):
	S[i] = S[i - 1] + A[i]
	S[i] %= K
d = defaultdict(list)
for i in range(N):
	d[(S[i] - i) % K].append(i)
ans = 0
for k in d:
	l = d[k]
	for i in range(len(l)):
		n = l[i]
		j = bisect.bisect_left(l, n + K)
		ans += j - i - 1
	if k == 1:
		j = bisect.bisect_left(l, K - 1)
		ans += j
print(ans)


from collections import defaultdict
(N, K) = map(int, input().split())
A = [int(c) % K - 1 for c in input().split()]
B = [0]
for c in A:
	B += [B[-1] + c]
dic = defaultdict(int)
ldic = defaultdict(int)
for i in range(min(K, N + 1)):
	c = B[i]
	dic[c % K] += 1
ans = 0
for i in range(1, N + 1):
	x = B[i - 1]
	ldic[x % K] += 1
	ans += dic[x % K] - ldic[x % K]
	if K + i - 1 <= N:
		dic[B[K + i - 1] % K] += 1
print(ans)


from collections import deque
(n, k) = map(int, input().split())
al = list(map(int, input().split()))
val_cnt = {}
val_cnt[0] = 1
val_q = deque([0])
if k == 1:
	print(0)
	exit()
ans = 0
curr_sum = 0
for i in range(n):
	curr_sum += al[i]
	curr_sum %= k
	val = (curr_sum - (i + 1)) % k
	val_cnt.setdefault(val, 0)
	ans += val_cnt[val]
	val_cnt[val] += 1
	val_q.append(val)
	if len(val_q) >= k:
		poped = val_q.popleft()
		val_cnt[poped] -= 1
print(ans)


from itertools import accumulate
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
B = accumulate([0] + A)
C = [(b - i) % K for (i, b) in enumerate(B)]
cnt = dict()
cnt[C[0]] = 1
res = 0
for i in range(1, N + 1):
	if i >= K:
		cnt[C[i - K]] = cnt.get(C[i - K], 0) - 1
	res += cnt.get(C[i], 0)
	cnt[C[i]] = cnt.get(C[i], 0) + 1
print(res)


from collections import Counter
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
A = list(map(lambda x: x % K - 1, A))
sa = [0] * (N + 1)
for i in range(1, N + 1):
	sa[i] = (sa[i - 1] + A[i - 1]) % K
c = Counter(sa[:K - 1])
ans = 0
for i in c.values():
	ans += i * (i - 1) // 2
for i in range(K - 1, N + 1):
	ans += c[sa[i]]
	c[sa[i - (K - 1)]] -= 1
	c[sa[i]] += 1
print(ans)


import queue
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
S = [0] * (N + 1)
for i in range(N):
	S[i + 1] = (S[i] + A[i] - 1) % K
v_set = set(S)
mp = {v: 0 for v in v_set}
ans = 0
q = queue.Queue()
for i in range(N + 1):
	ans += mp[S[i]]
	mp[S[i]] += 1
	q.put(S[i])
	if q.qsize() == K:
		mp[q.get()] -= 1
print(ans)


import bisect
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n - 1):
	a[i] -= 1
	a[i + 1] += a[i]
a[n - 1] -= 1
memo = {0: []}
for i in range(n):
	if a[i] % k not in memo.keys():
		memo[a[i] % k] = [i]
	else:
		memo[a[i] % k].append(i)
ans = bisect.bisect_left(memo[0], k - 1)
for i in memo.keys():
	for j in range(len(memo[i]) - 1):
		ans += bisect.bisect_left(memo[i], memo[i][j] + k) - 1 - j
print(ans)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
	a[i] -= 1
	a[i] %= k
b = [0]
for i in range(n):
	b.append((b[-1] + a[i]) % k)
ans = 0
now = {}
for i in range(n + 1):
	tmp = b[i]
	if tmp in now:
		ans += now[tmp]
		now[tmp] += 1
	else:
		now[tmp] = 1
	if i - k + 1 >= 0:
		now[b[i - k + 1]] -= 1
print(ans)


from collections import defaultdict as dd
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
S = [0] * (N + 1)
for i in range(1, N + 1):
	S[i] = S[i - 1] + A[i - 1] - 1
	S[i] %= K
B = dd(int)
cnt = 0
for j in range(1, N + 1):
	B[S[j - 1]] += 1
	if j - K >= 0:
		B[S[j - K]] -= 1
	cnt += B[S[j]]
print(cnt)


import sys
import numpy as np
from collections import defaultdict
sr = lambda : sys.stdin.readline().rstrip()
ir = lambda : int(sr())
lr = lambda : list(map(int, sr().split()))
(N, K) = lr()
A = np.array([1] + lr())
A = (A - 1) % K
Acum = A.cumsum() % K
counter = defaultdict(int)
answer = 0
for i in range(len(Acum)):
	x = Acum[i]
	answer += counter[x]
	counter[x] += 1
	if i >= K - 1:
		counter[Acum[i - (K - 1)]] -= 1
print(answer)


import collections
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
sa = [0]
for i in range(n):
	sa.append(sa[i] + a[i])
	sa[i + 1] -= 1
	sa[i + 1] %= k
cd = collections.defaultdict(lambda : 0)
res = 0
for i in range(n + 1):
	cd[sa[i]] += 1
	if i >= k:
		cd[sa[i - k]] -= 1
	res += cd[sa[i]] - 1
print(res)


(N, K) = map(int, input().split())
A = list(map(lambda x: int(x) % K, input().split()))
cum = [0] * (N + 1)
for i in range(N):
	cum[i + 1] = cum[i] + A[i]
x = [(cum[i] - i) % K for i in range(N + 1)]
dic = {}
ans = 0
for i in range(N + 1):
	if i >= K:
		dic[x[i - K]] -= 1
	ans += dic.get(x[i], 0)
	if not x[i] in dic:
		dic[x[i]] = 1
	else:
		dic[x[i]] += 1
print(ans)


from collections import defaultdict
(n, k) = map(int, input().split())
nums = [int(i) for i in input().split()]
nums = [0] + nums
for i in range(n):
	nums[i + 1] = (nums[i] + nums[i + 1] + k - 1) % k
ans = 0
d = defaultdict(int)
for i in range(n + 1):
	ans += d[nums[i]]
	d[nums[i]] += 1
	if i - (k - 1) >= 0:
		d[nums[i - (k - 1)]] -= 1
print(ans)


from itertools import accumulate
from collections import defaultdict
(N, K) = map(int, input().split())
A = [0] + [a - 1 for a in map(int, input().split())]
A_cum = list(accumulate(A))
A_cum = [a % K for a in A_cum]
ans = 0
dd = defaultdict(int)
q = []
for j in range(N + 1):
	ans += dd[A_cum[j]]
	dd[A_cum[j]] += 1
	q.append(A_cum[j])
	if len(q) == K:
		dd[q[0]] -= 1
		q.pop(0)
print(ans)


from collections import defaultdict
(N, K) = map(int, input().split())
(*A,) = map(int, input().split())
A = [0] + A
d = []
c = defaultdict(int)
x = 0
ans = 0
for (i, a) in enumerate(A):
	x += a - 1
	x %= K
	d.append(x)
	if i - K >= 0:
		c[d[i - K]] -= 1
	ans += c[x]
	c[x] += 1
print(ans)


from collections import defaultdict
from collections import deque
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
for i in range(N):
	A[i] -= 1
s = [0 for _ in range(N + 1)]
for i in range(N):
	s[i + 1] = (s[i] + A[i]) % K
d = defaultdict(int)
ans = 0
q = deque()
for j in range(N + 1):
	ans += d[s[j]]
	d[s[j]] += 1
	q.append(s[j])
	if len(q) == K:
		d[q[0]] -= 1
		q.popleft()
print(ans)


import itertools
from collections import defaultdict
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
A = [0] + [x - 1 for x in A]
Acum = list(itertools.accumulate(A))
Acum = [x % K for x in Acum]
counter = defaultdict(int)
answer = 0
for (i, x) in enumerate(Acum):
	answer += counter[x]
	counter[x] += 1
	if i >= K - 1:
		counter[Acum[i - K + 1]] -= 1
print(answer)


(M, K) = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
accum = [0]
d = {0: 1}
for (i, a) in enumerate(A):
	accum.append((accum[-1] + a - 1) % K)
	if i >= K - 1:
		d[accum[i - K + 1]] -= 1
	if accum[-1] in d:
		ans += d[accum[-1]]
		d[accum[-1]] += 1
	else:
		d[accum[-1]] = 1
print(ans)


from collections import defaultdict

def main():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	ruiseki = [0]
	d = defaultdict(int)
	d[0] = 1
	for i in range(n):
		if i - k + 1 >= 0:
			d[ruiseki[i - k + 1]] -= 1
		ruiseki.append((ruiseki[i] + a[i] - 1) % k)
		ans += d[ruiseki[i + 1]]
		d[ruiseki[i + 1]] += 1
	print(ans)
main()


import bisect
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
S = [0 for i in range(N + 1)]
for i in range(N):
	S[i + 1] = S[i] + A[i]
	S[i + 1] %= K
X = [(S[i] - i) % K for i in range(N + 1)]
D = dict()
for i in range(N + 1):
	if X[i] in D:
		D[X[i]].append(i)
	else:
		D[X[i]] = [i]
ans = 0
for k in D:
	for i in D[k]:
		L = bisect.bisect_left(D[k], i - K + 1)
		R = bisect.bisect_right(D[k], i + K - 1)
		ans += R - L - 1
print(ans // 2)


from itertools import accumulate
from collections import defaultdict
import bisect
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a = [0] + list(accumulate([(i - 1) % k for i in a]))
a = [i % k for i in a]
ans = 0
maps = defaultdict(list)
for (k1, v) in enumerate(a):
	maps[v].append(k1)
for i in range(n):
	v = a[i]
	ans += bisect.bisect_right(maps[v], i + k - 1) - bisect.bisect_right(maps[v], i)
print(ans)


(N, K) = map(int, input().split())
A = list(map(int, input().split()))
B = [a - 1 for a in A]
S = [0]
for b in B:
	S.append((S[-1] + b) % K)
from collections import Counter
C = Counter()
ANS = 0
for i in range(N + 1):
	ANS += C[S[i]]
	C[S[i]] += 1
	if i - K + 1 >= 0:
		C[S[i - K + 1]] -= 1
print(ANS)


from collections import defaultdict
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
if k == 1:
	print(0)
	exit()
s = [0]
for i in a:
	s.append((s[-1] + i - 1) % k)
d = defaultdict(int)
d[0] = 1
ans = 0
for r in range(1, n + 1):
	sr = s[r]
	if d[sr] > 0:
		ans += d[sr]
	d[sr] += 1
	l = r - k + 1
	if l >= 0:
		d[s[l]] -= 1
print(ans)


from collections import deque
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a = [i - 1 for i in a]
acc_a = [0 for i in range(n + 1)]
acc_a[0] = 0
acc_a[1] = a[0] % k
for i in range(2, len(a) + 1):
	acc_a[i] = (a[i - 1] + acc_a[i - 1]) % k
ans = 0
count = {}
q = deque()
for i in acc_a:
	if i not in count:
		count[i] = 0
	ans += count[i]
	count[i] += 1
	q.append(i)
	if len(q) == k:
		count[q.popleft()] -= 1
print(ans)


(n, k) = [int(_) for _ in input().split()]
a = [int(_) for _ in input().split()]
s = [0]
for i in range(len(a)):
	s.append(s[-1] + a[i])
for i in range(len(s)):
	s[i] = (s[i] - i) % k
d = {0: 1}
ans = 0
for j in range(1, n + 1):
	if s[j] in d:
		d[s[j]] += 1
	else:
		d[s[j]] = 1
	if j >= k:
		d[s[j - k]] -= 1
	ans += d[s[j]] - 1
print(ans)


from collections import defaultdict
import bisect
(n, k) = list(map(int, input().split()))
a = [1] + list(map(int, input().split()))
d = defaultdict(list)
for i in range(n + 1):
	a[i] -= 1
d[a[0] % k].append(0)
for i in range(n):
	a[i + 1] += a[i]
	d[a[i + 1] % k].append(i + 1)
ans = 0
for l in list(d.values()):
	for (i, idx) in enumerate(l):
		ans += bisect.bisect_left(l, idx + k) - i - 1
print(ans)


from collections import defaultdict

def main():
	(N, K) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	S = [0] * (N + 1)
	for i in range(1, N + 1):
		S[i] = S[i - 1] + A[i - 1]
	T = [(s - i) % K for (i, s) in enumerate(S)]
	counter = defaultdict(int)
	ans = 0
	for j in range(N + 1):
		if j >= K:
			counter[T[j - K]] -= 1
		ans += counter[T[j]]
		counter[T[j]] += 1
	print(ans)
main()


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
dp = [0]
mp = {0: 1}
ans = 0
for t in range(n):
	i = a[t]
	if t >= k - 1:
		mp[dp[-k]] -= 1
	num = (dp[-1] + i - 1) % k
	if num in mp.keys():
		ans += mp[num]
		mp[num] += 1
	else:
		mp[num] = 1
	dp.append(num)
print(ans)


(n, k) = map(int, input().split())
a = list(map(lambda x: (int(x) - 1) % k, input().split()))
a_ = 0
cs_a = [0]
for ai in a:
	a_ += ai
	a_ %= k
	cs_a.append(a_)
ans = 0
from collections import defaultdict
d = defaultdict(int)
for i in range(n + 1):
	ans += d[cs_a[i]]
	d[cs_a[i]] += 1
	if i >= k - 1:
		d[cs_a[i - k + 1]] -= 1
print(ans)


(n, k) = list(map(int, input().split()))
a = [0] + list(map(int, input().split()))
for i in range(n):
	a[i + 1] += a[i]
	a[i + 1] %= k
cnt = {}
ans = 0
for i in range(n + 1):
	left = i - k
	if left >= 0:
		ldiff = (a[left] - left) % k
		cnt[ldiff] -= 1
	x = (a[i] - i) % k
	if x < 0:
		x += k
	if x not in cnt:
		cnt[x] = 0
	ans += cnt[x]
	cnt[x] += 1
print(ans)


from collections import defaultdict
from bisect import bisect_right
(n, k) = list(map(int, input().split()))
alst = list(map(int, input().split()))
dd = defaultdict(list)
dd[0].append(0)
total = 0
for (i, num) in enumerate(alst, start=1):
	total += num
	total %= k
	app = total - i
	app %= k
	dd[app].append(i)
ans = 0
for (_, lst) in list(dd.items()):
	for (i, num) in enumerate(lst):
		num2 = num + k - 1
		pos = bisect_right(lst, num2)
		ans += pos - i - 1
print(ans)


import collections

def main():
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	d = collections.defaultdict(int)
	prefix = [0]
	for i in range(N):
		prefix.append(prefix[-1] + A[i])
	ans = 0
	for j in range(N + 1):
		v = (prefix[j] - j) % K
		ans += d[v]
		d[v] += 1
		if j >= K - 1:
			d[(prefix[j - K + 1] - (j - K + 1)) % K] -= 1
	return ans
print(main())


def main():
	(N, K) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	s = 0
	d = {}
	d[0] = {0}
	r = 0
	l = [0] * (N + 1)
	for (i, v) in enumerate(A, start=1):
		if i - K >= 0:
			x = l[i - K]
			d[x].remove(i - K)
		s += v % K
		s %= K
		t = (s - i) % K
		l[i] = t
		if t in d:
			r += len(d[t])
			d[t].add(i)
		else:
			d[t] = {i}
	return r
print(main())


from bisect import *
(n, k) = map(int, input().split())
A = list(map(int, input().split()))
s = 0
sl = {0: [0]}
for i in range(n):
	s += A[i] - 1
	s %= k
	if s not in sl.keys():
		sl[s] = []
	sl[s].append(i + 1)
ans = 0
for ls in sl.values():
	for (i, l) in enumerate(ls):
		x = bisect_right(ls, l + k - 1)
		ans += x - i - 1
print(ans)


from collections import defaultdict
(N, K, *A) = map(int, open(0).read().split())
x = [0] * (N + 1)
for i in range(N):
	x[i + 1] = x[i] + A[i]
y = [(x[i] - i) % K for i in range(N + 1)]
ctr = defaultdict(int)
ans = 0
for j in range(N + 1):
	ans += ctr[y[j]]
	ctr[y[j]] += 1
	if j - K + 1 >= 0:
		ctr[y[j - K + 1]] -= 1
print(ans)


from itertools import accumulate
from collections import Counter
(n, k, *a) = map(int, open(0).read().split())
a = [x % k - 1 for x in a]
a = [0] + [x % k for x in accumulate(a)]
d = Counter()
ans = 0
for (l, r) in zip([k] * min(k, n + 1) + a, a):
	d[l] -= 1
	ans += d[r]
	d[r] += 1
print(ans)


(N, K) = map(int, input().split())
A = list(map(lambda x: int(x) - 1, input().split()))
sa = [0]
for a in A:
	sa.append((sa[-1] + a) % K)
d = {0: 1}
ans = 0
for i in range(1, N + 1):
	if i >= K:
		d[sa[i - K]] -= 1
	v = d.get(sa[i], 0)
	ans += v
	d[sa[i]] = v + 1
print(ans)


from collections import defaultdict
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
	a[i] -= 1
mods = defaultdict(int)
cnt = 0
tmp = 0
for i in range(min(k - 1, n)):
	tmp = (tmp + a[i]) % k
	mods[tmp] += 1
	cnt += 1
ans = 0
tmp2 = 0
for i in range(n):
	ans += mods[tmp2]
	tmp2 = (tmp2 + a[i]) % k
	mods[tmp2] -= 1
	if cnt < n:
		tmp = (tmp + a[cnt]) % k
		mods[tmp] += 1
		cnt += 1
print(ans)


from collections import defaultdict
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
cum_sum = [0] * (n + 1)
for i in range(n):
	cum_sum[i + 1] = (cum_sum[i] + a[i] - 1) % k
D = defaultdict(int)
count = 0
for i in range(n + 1):
	count += D[cum_sum[i]]
	D[cum_sum[i]] += 1
	if i - k + 1 >= 0:
		D[cum_sum[i - k + 1]] -= 1
print(count)


from collections import defaultdict
import bisect
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
aa = [0]
cur = 0
for i in a:
	cur = (cur + i - 1) % k
	aa.append(cur)
d = defaultdict(list)
for i in range(n + 1):
	d[aa[i]].append(i)
ans = 0
for i in d.values():
	for j in i:
		ans += bisect.bisect_right(i, j + k - 1) - bisect.bisect_right(i, j)
print(ans)


from collections import defaultdict
(n, k) = map(int, input().split())
A = list(map(int, input().split()))
S = [0] * (n + 1)
for i in range(n):
	S[i + 1] = S[i] + A[i]
f = lambda n: (S[n] - n) % k
C = defaultdict(int)
ans = 0
for i in range(n):
	C[f(i)] += 1
	j = i - k + 1
	if 0 <= j:
		C[f(j)] -= 1
	ans += C[f(i + 1)]
print(ans)


import sys
input = sys.stdin.readline
from collections import *
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
acc = [0]
for Ai in A:
	acc.append(acc[-1] + Ai)
cnt = defaultdict(int)
ans = 0
for i in range(N + 1):
	ans += cnt[(acc[i] - i) % K]
	cnt[(acc[i] - i) % K] += 1
	if i >= K - 1:
		j = i - (K - 1)
		cnt[(acc[j] - j) % K] -= 1
print(ans)


from collections import defaultdict as dd
from itertools import accumulate
(N, K) = map(int, input().split())
As = [0] + list(map(int, input().split()))
S = list(accumulate(As))
ans = 0
counts = dd(int)
counts[0] = 1
for j in range(1, N + 1):
	if j >= K:
		counts[(S[j - K] - (j - K)) % K] -= 1
	t = (S[j] - j) % K
	ans += counts[t]
	counts[t] += 1
print(ans)


from itertools import accumulate
from collections import defaultdict
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
A = [a - 1 for a in A]
S = [0] + list(accumulate(A))
S = [s % K for s in S]
ans = 0
counter = defaultdict(int)
for (i, s) in enumerate(S):
	ans += counter[s]
	counter[s] += 1
	if i - K + 1 >= 0:
		counter[S[i - K + 1]] -= 1
print(ans)


from collections import deque, defaultdict
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
Si_m_i = [0]
total = 0
temp = 0
for i in range(N):
	total += A[i]
	temp = (total - i - 1) % K
	Si_m_i.append(temp)
ret = 0
d = defaultdict(deque)
for i in range(N + 1):
	pair = Si_m_i[i]
	temp = d[pair]
	while temp and i - temp[0] >= K:
		temp.popleft()
	ret += len(temp)
	d[Si_m_i[i]].append(i)
print(ret)


import numpy as np
from collections import defaultdict, deque
(N, K) = list(map(int, input().split()))
A = np.array([1] + list(map(int, input().split()))) - 1
Acs = np.cumsum(A)
Acs %= K
ans = 0
cnt = defaultdict(deque)
for (i, c) in enumerate(Acs):
	cnt[c].append(i)
	while cnt[c]:
		if i - cnt[c][0] > K - 1:
			cnt[c].popleft()
		else:
			break
	ans += len(cnt[c]) - 1
print(ans)


from collections import defaultdict
from itertools import accumulate

def solve():
	(N, K, *A) = list(map(int, open(0).read().split()))
	Acumsum = [0] + list(accumulate(A))
	si = [(Acumsum[i] - i) % K for i in range(N + 1)]
	counter = defaultdict(int)
	ans = 0
	for j in range(N):
		counter[si[j]] += 1
		if 0 <= j - K + 1:
			counter[si[j - K + 1]] -= 1
		ans += counter[si[j + 1]]
	print(ans)

def __starting_point():
	solve()
__starting_point()


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import itertools
from collections import defaultdict
(N, K, *A) = map(int, read().split())
A = [0] + [x - 1 for x in A]
Acum = list(itertools.accumulate(A))
Acum = [x % K for x in Acum]
counter = defaultdict(int)
answer = 0
for (i, x) in enumerate(Acum):
	answer += counter[x]
	counter[x] += 1
	if i >= K - 1:
		counter[Acum[i - K + 1]] -= 1
print(answer)


(N, K) = map(int, input().split())
A = [0] + [int(a) - 1 for a in input().split()]
for i in range(1, N + 1):
	A[i] = (A[i] + A[i - 1]) % K
D = {0: 1}
ans = 0
for i in range(1, N + 1):
	if i >= K:
		D[A[i - K]] -= 1
	a = A[i]
	if a not in D:
		D[a] = 0
	ans += D[a]
	D[a] += 1
print(ans)


import sys
input = sys.stdin.readline
from collections import deque
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
B = [0]
for a in A:
	b = (B[-1] + (a - 1)) % K
	B.append(b)
ans = 0
dic = {}
for (i, b) in enumerate(B):
	if b in dic:
		dic[b].append(i)
	else:
		dic[b] = deque()
		dic[b].append(i)
	while len(dic[b]) > 0 and dic[b][0] <= i - K:
		dic[b].popleft()
	ans += len(dic[b]) - 1
print(ans)


from itertools import accumulate
from collections import defaultdict
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
acc = [0] + list(accumulate(a))
sm = [(e - i) % k for (i, e) in enumerate(acc)]
d = defaultdict(int)
ans = 0
for r in range(1, n + 1):
	if r - k >= 0:
		e = sm[r - k]
		d[e] -= 1
	e = sm[r - 1]
	d[e] += 1
	e = sm[r]
	ans += d[e]
print(ans)


from collections import defaultdict
(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
d = defaultdict(int)
sa = [0] * (n + 1)
for i in range(n):
	sa[i + 1] = sa[i] + a[i]
	sa[i + 1] %= k
ans = 0
for i in range(n + 1):
	v = sa[i] - i
	v %= k
	ans += d[v]
	d[v] += 1
	if 0 <= i - k + 1:
		vv = sa[i - k + 1] - (i - k + 1)
		vv %= k
		d[vv] -= 1
print(ans)


(n, k, *a) = map(int, open(0).read().split())
a = [0] + a
for i in range(n):
	a[i + 1] = (a[i + 1] - 1 + a[i]) % k
d = {}
c = 0
for (i, b) in enumerate(a):
	v = d.get(b, 0)
	c += v
	d[b] = v + 1
	j = i - k + 1
	if j >= 0:
		d[a[j]] = d.get(a[j], 0) - 1
print(c)


(n, k) = map(int, input().split())
A = [int(i) for i in input().split()]
ans = 0
AA = [(A[0] - 1) % k]
for i in range(1, n):
	AA.append((AA[-1] + A[i] - 1) % k)
import collections
d = collections.defaultdict(int)
d[0] += 1
for i in range(n):
	if i + 1 == k:
		d[0] -= 1
	elif i + 1 >= k:
		d[AA[i - k]] = max(0, d[AA[i - k]] - 1)
	ans += d[AA[i]]
	d[AA[i]] += 1
print(ans)


(N, K) = map(int, input().split())
A = list(map(int, input().split()))
for i in range(1, N):
	A[i] += A[i - 1]
for i in range(N):
	A[i] -= i + 1
	A[i] %= K
A = [0] + A
D = {}
ans = 0
for j in range(1, N + 1):
	D[A[j - 1]] = D.get(A[j - 1], 0) + 1
	if j - K >= 0:
		D[A[j - K]] -= 1
	ans += D.get(A[j], 0)
print(ans)


(N, K) = map(int, input().split())
A = list(map(int, input().split()))
S = [0 for i in range(N + 1)]
for i in range(1, N + 1):
	S[i] = S[i - 1] + A[i - 1]
cnt = 0
dict1 = {}
dict1[0] = 1
for j in range(1, N + 1):
	if j - K >= 0:
		dict1[(S[j - K] - j + K) % K] -= 1
	if (S[j] - j) % K in dict1:
		cnt += dict1[(S[j] - j) % K]
		dict1[(S[j] - j) % K] += 1
	else:
		dict1[(S[j] - j) % K] = 1
print(cnt)


from queue import Queue
from collections import defaultdict
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
	a[i] -= 1
s = [0] * (n + 1)
for i in range(n):
	s[i + 1] = (s[i] + a[i]) % k
d = defaultdict(int)
ans = 0
q = Queue()
for j in range(n + 1):
	ans += d[s[j]]
	d[s[j]] += 1
	q.put(s[j])
	if q.qsize() == k:
		d[q.get()] -= 1
print(ans)


(n, k) = map(int, input().split())
nums = list(map(int, input().split()))
sums = [0]
for x in nums:
	sums.append(sums[-1] + x)
a = [(sums[i] - i) % k for i in range(len(sums))]
res = 0
memo = {}
i = 0
for j in range(len(a)):
	memo[a[j]] = memo.get(a[j], 0) + 1
	if j - i + 1 > k:
		memo[a[i]] -= 1
		i += 1
	res += memo[a[j]] - 1
print(res)


(n, k) = map(int, input().split())
l = [0] + [i % k - 1 for i in list(map(int, input().split()))]
from itertools import accumulate
l = list(accumulate(l))
import collections
d = collections.defaultdict(int)
d[0] += 1
ans = 0
for i in range(1, n + 1):
	if i >= k:
		d[l[i - k] % k] -= 1
	ans += d[l[i] % k]
	d[l[i] % k] += 1
print(ans)


import sys
sys.setrecursionlimit(2147483647)
INF = float('inf')
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()
from collections import defaultdict

def resolve():
	(n, k) = map(int, input().split())
	A = list(map(lambda x: int(x) - 1, input().split()))
	S = [0] * (n + 1)
	for i in range(n):
		S[i + 1] = S[i] + A[i]
		S[i + 1] %= k
	C = defaultdict(int)
	ans = 0
	for i in range(n + 1):
		ans += C[S[i]]
		C[S[i]] += 1
		if i - k + 1 >= 0:
			C[S[i - k + 1]] -= 1
	print(ans)
resolve()


(n, k) = map(int, input().split())
a = [0] + list(map(int, input().split()))
for i in range(n):
	a[i + 1] = (a[i] + a[i + 1] - 1) % k
d = dict()
ans = 0
for i in range(n + 1):
	if i >= k:
		d[a[i - k]] -= 1
	if a[i] in d:
		ans += d[a[i]]
		d[a[i]] += 1
	else:
		d[a[i]] = 1
print(ans)


import sys
input = sys.stdin.readline
from itertools import accumulate
(N, K) = map(int, input().split())
A = map(int, input().split())
B = accumulate(A)
C = [0] + [(b - i) % K for (i, b) in enumerate(B, start=1)]
cnt = dict()
cnt[C[0]] = 1
res = 0
for i in range(1, N + 1):
	if i >= K:
		cnt[C[i - K]] = cnt.get(C[i - K], 0) - 1
	res += cnt.get(C[i], 0)
	cnt[C[i]] = cnt.get(C[i], 0) + 1
print(res)


def main():
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	B = [0] * (N + 1)
	b = 0
	for (i, a) in enumerate(A):
		b += a - 1
		b %= K
		B[i + 1] = b
	Q = {}
	X = 0
	for (i, b) in enumerate(B):
		if i >= K:
			Q[B[i - K]] -= 1
		if b in Q:
			X += Q[b]
			Q[b] += 1
		else:
			Q[b] = 1
	print(X)
main()


from collections import defaultdict
(n, k) = map(int, input().split())
l = list(map(int, input().split()))
mod = [0]
for i in range(n):
	a = (l[i] - 1) % k
	mod.append((mod[-1] + a) % k)
dic = defaultdict(int)
ans = 0
for i in range(n + 1):
	if i < k:
		ans += dic[mod[i]]
		dic[mod[i]] += 1
	else:
		dic[mod[i - k]] -= 1
		ans += dic[mod[i]]
		dic[mod[i]] += 1
print(ans)


from itertools import accumulate
from collections import defaultdict
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
A_cum = [0] + list(accumulate(A))
ans = 0
dd = defaultdict(int)
q = []
for (i, a) in enumerate(A_cum):
	a -= i
	a %= K
	if i - K >= 0:
		dd[q[i - K]] -= 1
	ans += dd[a]
	dd[a] += 1
	q.append(a)
print(ans)


from itertools import accumulate
(n, k) = map(int, input().split())
A = [int(i) for i in input().split()]
S = list(accumulate(A))
S.insert(0, 0)
L = [(s - i) % k for (i, s) in enumerate(S)]

def f(l):
	return sum([x * (x - 1) // 2 for x in l])
from collections import Counter
ans = 0
d = Counter(L[1:k])
for i in range(n):
	ans += d[L[i]]
	d[L[i + 1]] -= 1
	if i + k <= n:
		d[L[i + k]] += 1
print(ans)


from collections import defaultdict
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a_cs = [0] * (n + 1)
for i in range(n):
	a_cs[i + 1] = a_cs[i] + a[i]
ans = 0
d = defaultdict(int)
for j in range(n + 1):
	if j - k >= 0:
		d[(a_cs[j - k] - (j - k)) % k] -= 1
	ans += d[(a_cs[j] - j) % k]
	d[(a_cs[j] - j) % k] += 1
print(ans)


from collections import defaultdict
(N, K) = list(map(int, input().split()))
A = list(map(int, input().split()))
Am = [a - 1 for a in A]
Acc = [0] * (N + 1)
for i in range(N):
	Acc[i + 1] = (Acc[i] + Am[i]) % K
d = defaultdict(int)
(l, r) = (0, 0)
ans = 0
while r <= N:
	a = Acc[r]
	ans += d[a]
	d[a] += 1
	r += 1
	if r - l >= K:
		d[Acc[l]] -= 1
		l += 1
print(ans)


from itertools import accumulate
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
s = [0] + list(accumulate(a))

def f(x):
	return (x + n * k) % k
ans = 0
dic = {}
for i in range(n + 1):
	if i >= k:
		prev = f(s[i - k] - (i - k))
		dic[prev] -= 1
	cur = f(s[i] - i)
	if cur in dic:
		ans += dic[cur]
		dic[cur] += 1
	else:
		dic[cur] = 1
print(ans)


from bisect import bisect_right
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
for i in range(N):
	A[i] = (A[i] - 1) % K
B = [0]
for a in A:
	B.append((B[-1] + a) % K)
dic = {}
for (i, b) in enumerate(B):
	if not b in dic.keys():
		dic[b] = [i]
	else:
		dic[b].append(i)
ans = 0
for L in dic.values():
	for i in range(len(L)):
		j = bisect_right(L, L[i] + K - 1)
		ans += j - i - 1
print(ans)


import itertools
from collections import defaultdict
(n, k) = map(int, input().split())
lis = list(map(int, input().split()))
lis = [0] + [lis[i] - 1 for i in range(n)]
ruiseki = list(itertools.accumulate(lis))
ruiseki = [x % k for x in ruiseki]
counter = defaultdict(int)
ans = 0
for (i, x) in enumerate(ruiseki):
	ans += counter[x]
	counter[x] += 1
	if i >= k - 1:
		counter[ruiseki[i - k + 1]] -= 1
print(ans)


from collections import defaultdict
(N, K, *A) = map(int, open(0).read().split())
S = [0] * (N + 1)
for i in range(N):
	S[i + 1] = S[i] + A[i]
d = defaultdict(int)
ans = 0
for j in range(N + 1):
	v = (S[j] - j) % K
	ans += d[v]
	d[v] += 1
	if j >= K - 1:
		d[(S[j - K + 1] - (j - K + 1)) % K] -= 1
print(ans)


from collections import defaultdict
import numpy as np
(N, K) = list(map(int, input().split()))
A = [0] + list(map(int, input().split()))
A = np.array(A)
A %= K
A = A.cumsum()
tmp = np.arange(N + 1)
B = (A - tmp) % K
ans = 0
d = defaultdict(int)
for i in range(min(K, N + 1)):
	x = B[i]
	ans += d[x]
	d[x] += 1
if N > K:
	for i in range(K, N + 1):
		x = B[i]
		y = B[i - K]
		d[y] -= 1
		ans += d[x]
		d[x] += 1
print(ans)


from itertools import accumulate
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
x = [0] + list(accumulate(a))
mods = dict()
for i in range(n + 1):
	now = (x[i] - i) % k
	if now in mods:
		mods[now].append(i)
	else:
		mods[now] = [i]
ans = 0
from bisect import bisect_left
for i in mods:
	l = len(mods[i])
	for j in range(l):
		b = bisect_left(mods[i], mods[i][j] + k) - 1
		ans += b - j
print(ans)


(N, K) = map(int, input().split())
S = []
d = {}
A = list(map(int, input().split()))
ans = 0
sum = 0
for i in range(1, N + 1):
	sum += A[i - 1] % K
	s = (sum - i) % K
	if i > K:
		x = S.pop(0)
		d[x] -= 1
	elif i < K:
		if s == 0:
			ans += 1
	if s not in d:
		d[s] = 0
	ans += d[s]
	d[s] += 1
	S.append(s)
print(ans)


(n, k) = map(int, input().split())
a = [0] + list(map(int, input().split()))
cnt = {0: 1}
ans = 0
for i in range(1, n + 1):
	left = i - k
	if left >= 0:
		ldif = (a[left] - left) % k
		if ldif < 0:
			ldif += k
		cnt[ldif] -= 1
	a[i] += a[i - 1]
	dif = (a[i] - i) % k
	if dif < 0:
		dif += k
	if dif not in cnt:
		cnt[dif] = 0
	ans += cnt[dif]
	cnt[dif] += 1
print(ans)


from collections import *
import copy
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
lst = [0]
for i in range(0, N):
	lst.append((A[i] % K + lst[i]) % K)
for i in range(len(lst)):
	lst[i] -= i
	lst[i] %= K
dic = {}
count = 0
for i in range(0, len(lst)):
	if lst[i] in dic:
		count += dic[lst[i]]
		dic[lst[i]] += 1
	else:
		dic.update({lst[i]: 1})
	a = i - K + 1
	if a >= 0:
		dic[lst[a]] -= 1
print(count)


from collections import Counter
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
S = [0] * (N + 1)
for (i, a) in enumerate(A):
	S[i + 1] = (S[i] + a - 1) % K
C = Counter()
ans = 0
for j in range(1, N + 1):
	C[S[j - 1]] += 1
	if j - K >= 0:
		C[S[j - K]] -= 1
	ans += C[S[j]]
print(ans)


import sys
from itertools import accumulate
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7

def resolve():
	(n, k) = list(map(int, input().split()))
	A = list([int(x) - 1 for x in input().split()])
	S = [0] + list(accumulate(A))
	S = [s % k for s in S]
	cnt = defaultdict(int)
	res = 0
	for i in range(n + 1):
		if i >= k:
			cnt[S[i - k]] -= 1
		res += cnt[S[i]]
		cnt[S[i]] += 1
	print(res)

def __starting_point():
	resolve()
__starting_point()


from collections import defaultdict
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
	a[i] -= 1
	a[i] %= k
S = [0]
for i in range(n):
	S.append((S[-1] + a[i]) % k)
ans = 0
dic = defaultdict(int)
dic[0] = 1
for i in range(1, n + 1):
	if i >= k:
		dic[S[i - k]] -= 1
	ans += max(0, dic[S[i]])
	dic[S[i]] += 1
print(ans)


from collections import defaultdict
(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
d = [0]
for i in a:
	a_i = (d[-1] + i) % k
	d.append(a_i)
ans = 0
counter = defaultdict(int)
for (i, s) in enumerate(d):
	ans += counter[(s - i) % k]
	counter[(s - i) % k] += 1
	if i - k + 1 >= 0:
		counter[(d[i - k + 1] - i + k - 1) % k] -= 1
print(ans)


from collections import Counter
(N, K) = list(map(int, input().split()))
(*A,) = list(map(int, input().split()))
MOD = 10 ** 9 + 7
S = [0] * (N + 1)
c = Counter()
c[0] = 1
ans = 0
for i in range(N):
	S[i + 1] = (S[i] + A[i] - 1) % K
	if i + 1 - K >= 0:
		c[S[i + 1 - K]] -= 1
	ans += c[S[i + 1]]
	c[S[i + 1]] += 1
print(ans)


(N, K) = map(int, input().split())
A = list(map(int, input().split()))
for i in range(1, N):
	A[i] += A[i - 1]
A.append(0)
A.sort()
A = [((A[i] - i) % K, i) for i in range(0, N + 1)]
A.sort()
count = 0
s = 0
t = 1
while N >= t and N >= s:
	if A[t][0] == A[s][0] and K > A[t][1] - A[s][1]:
		t += 1
		if t == N + 1:
			count += (t - s) * (t - s - 1) // 2
	else:
		count += t - s - 1
		s += 1
		if s == t:
			t += 1
print(count)


def main():
	(N, K) = [int(i) for i in input().split()]
	A = [int(i) for i in input().split()]
	v = {0: 1}
	n = [0]
	r = 0
	t = 0
	for (i, a) in enumerate(A, 1):
		if i >= K:
			v[n[i - K]] -= 1
		t += a
		j = (t - i) % K
		r += v.get(j, 0)
		v[j] = v.get(j, 0) + 1
		n.append(j)
	return r
print(main())


import sys
import bisect
input = lambda : sys.stdin.readline().rstrip()

def solve():
	(N, K) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	S = [0 for _ in range(N + 1)]
	for i in range(N):
		S[i + 1] = S[i] + A[i] - 1
	d = dict()
	for i in range(N + 1):
		k = S[i] % K
		if k in d:
			d[k].append(i)
		else:
			d[k] = [i]
	ans = 0
	for (k, v) in list(d.items()):
		if len(v) <= 1:
			continue
		else:
			for i in range(len(v)):
				s = v[i] + K - 1
				si = bisect.bisect_right(v, s)
				ans += si - i - 1
	print(ans)

def __starting_point():
	solve()
__starting_point()


from collections import defaultdict
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
A = [a - 1 for a in A]
Acum = [0]
for a in A:
	Acum.append((Acum[-1] + a) % K)
answer = 0
counter = defaultdict(int)
for (i, ai) in enumerate(Acum):
	answer += counter[ai]
	counter[ai] += 1
	if i - K + 1 >= 0:
		counter[Acum[i - K + 1]] -= 1
print(answer)


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
arr = [i - 1 for i in arr]
acum = [0]
for i in range(n):
	acum.append(acum[-1] + arr[i])
acum = [i % k for i in acum]
ans = 0
dic = {}
for i in range(n + 1):
	if acum[i] % k not in dic:
		dic[acum[i]] = 1
	else:
		ans += dic[acum[i]]
		dic[acum[i]] += 1
	if i >= k - 1:
		dic[acum[i - k + 1]] -= 1
print(ans)


from collections import defaultdict
from itertools import accumulate
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
A_acc = [0] + list(accumulate(A))
ans = 0
D = defaultdict(int)
for l in range(N + 1):
	t = (A_acc[l] - l) % K
	if l >= K:
		r = A_acc[l - K] - (l - K)
		D[r % K] -= 1
	ans += D[t]
	D[t] += 1
print(ans)


import math
import numpy as np
import decimal
import collections
import itertools
import sys
import random

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.par = [-1 for i in range(self.n)]

	def find(self, x):
		if self.par[x] < 0:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]

	def unite(self, x, y):
		p = self.find(x)
		q = self.find(y)
		if p == q:
			return None
		if p > q:
			(p, q) = (q, p)
		self.par[p] += self.par[q]
		self.par[q] = p

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def size(self, x):
		return -self.par[self.find(x)]

def prime_numbers(x):
	if x < 2:
		return []
	prime_numbers = [i for i in range(x)]
	prime_numbers[1] = 0
	for prime_number in prime_numbers:
		if prime_number > math.sqrt(x):
			break
		if prime_number == 0:
			continue
		for composite_number in range(2 * prime_number, x, prime_number):
			prime_numbers[composite_number] = 0
	return [prime_number for prime_number in prime_numbers if prime_number != 0]

def is_prime(x):
	if x < 2:
		return False
	if x == 2 or x == 3 or x == 5:
		return True
	if x % 2 == 0 or x % 3 == 0 or x % 5 == 0:
		return False
	prime_number = 7
	difference = 4
	while prime_number <= math.sqrt(x):
		if x % prime_number == 0:
			return False
		prime_number += difference
		difference = 6 - difference
	return True

def prime_factorize(n):
	res = []
	while n % 2 == 0:
		res.append(2)
		n //= 2
	f = 3
	while f ** 2 <= n:
		if n % f == 0:
			res.append(f)
			n //= f
		else:
			f += 2
	if n != 1:
		res.append(n)
	return res
mod = 10 ** 9 + 7

class nCr:

	def __init__(self, n):
		self.n = n
		self.fa = [1] * (self.n + 1)
		self.fi = [1] * (self.n + 1)
		for i in range(1, self.n + 1):
			self.fa[i] = self.fa[i - 1] * i % mod
			self.fi[i] = pow(self.fa[i], mod - 2, mod)

	def comb(self, n, r):
		if n < r:
			return 0
		if n < 0 or r < 0:
			return 0
		return self.fa[n] * self.fi[r] % mod * self.fi[n - r] % mod

def extgcd(a, b, d=0):
	g = a
	if b == 0:
		(x, y) = (1, 0)
	else:
		(x, y, g) = extgcd(b, a % b)
		(x, y) = (y, x - a // b * y)
	return (x, y, g)

class BinaryIndexedTree:

	def __init__(self, n):
		self.n = n
		self.BIT = [0] * (self.n + 1)

	def add(self, i, x):
		while i <= self.n:
			self.BIT[i] += x
			i += i & -i

	def query(self, i):
		res = 0
		while i > 0:
			res += self.BIT[i]
			i -= i & -i
		return res

class AssociativeArray:

	def __init__(self, q):
		self.dic = dict()
		self.q = q

	def solve(self):
		for i in range(self.q):
			Query = list(map(int, input().split()))
			if Query[0] == 0:
				(x, y, z) = Query
				self.dic[y] = z
			else:
				(x, y) = Query
				if y in self.dic:
					print(self.dic[y])
				else:
					print(0)

def floor_sum(n, m, a, b):
	res = 0
	if a >= m:
		res += (n - 1) * n * (a // m) // 2
		a %= m
	if b >= m:
		res += n * (b // m)
		b %= m
	y_max = (a * n + b) // m
	x_max = y_max * m - b
	if y_max == 0:
		return res
	res += y_max * (n + -x_max // a)
	res += floor_sum(y_max, a, m, (a - x_max % a) % a)
	return res

def z_algorithm(s):
	str_len = len(s)
	res = [0] * str_len
	res[str_len - 1] = str_len
	(i, j) = (1, 0)
	while i < str_len:
		while i + j < str_len and s[i + j] == s[j]:
			j += 1
		res[i] = j
		if j == 0:
			i += 1
			continue
		k = 1
		while i + k < str_len and j > res[k] + k:
			res[i + k] = res[k]
			k += 1
		i += k
		j -= k
	return res

class Manacher:

	def __init__(self, s):
		self.s = s

	def coustruct(self):
		(i, j) = (0, 0)
		s_len = len(self.s)
		res = [0] * s_len
		while i < s_len:
			while i - j >= 0 and i + j < s_len and (self.s[i - j] == self.s[i + j]):
				j += 1
			res[i] = j
			k = 1
			while i - k >= 0 and k + res[i - k] < j:
				k += 1
			i += k
			j -= k

def mod_sqrt(a, p):
	if a == 0:
		return 0
	if p == 2:
		return 1
	k = (p - 1) // 2
	if pow(a, k, p) != 1:
		return -1
	while True:
		n = random.randint(2, p - 1)
		r = (n ** 2 - a) % p
		if r == 0:
			return n
		if pow(r, k, p) == p - 1:
			break
	k += 1
	(w, x, y, z) = (n, 1, 1, 0)
	while k:
		if k % 2:
			(y, z) = (w * y + r * x * z, x * y + w * z)
		(w, x) = (w * w + r * x * x, 2 * w * x)
		w %= p
		x %= p
		y %= p
		z %= p
		k >>= 1
	return y
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
for i in range(1, n):
	a[i] += a[i - 1]
for i in range(n):
	a[i] -= i + 1
	a[i] %= k
a = [0] + a
dic = {}
ans = 0
for i in range(n):
	dic[a[i]] = dic.get(a[i], 0) + 1
	if i - k + 1 >= 0:
		dic[a[i - k + 1]] -= 1
	ans += dic.get(a[i + 1], 0)
print(ans)


import sys
input = sys.stdin.readline
(N, K) = map(int, input().strip().split(' '))
A = list(map(int, input().strip().split(' ')))
A = [0] + A
for i in range(1, N + 1):
	A[i] += A[i - 1]
	A[i - 1] -= i - 1
A[N] -= N
rem_count = {}
rem_count[0] = 1
ans = 0
for i in range(1, N + 1):
	if i - K >= 0:
		rem_count[A[i - K] % K] -= 1
	if A[i] % K in rem_count:
		ans += rem_count[A[i] % K]
		rem_count[A[i] % K] += 1
	else:
		rem_count[A[i] % K] = 1
print(ans)


from collections import defaultdict
from itertools import accumulate
(n, k) = map(int, input().split())
A = list(map(int, input().split()))
S = [0] + list(accumulate(A))
Q = [(S[i] - i) % k for i in range(n + 1)]
d = defaultdict(int)
ans = 0
for j in range(n):
	d[Q[j]] += 1
	if j - k + 1 >= 0:
		d[Q[j - k + 1]] -= 1
	ans += d[Q[j + 1]]
print(ans)


(N, K) = list(map(int, input().split()))
A = list(map(int, input().split()))
s = 0
B = [0]
C = {0: [0]}
for (i, a) in enumerate(A):
	s = (s + a) % K
	n = (s - i - 1) % K
	B.append(n)
	if n not in C:
		C[n] = []
	C[n].append(i + 1)
ans = 0
for (k, v) in C.items():
	if len(v) <= 1:
		continue
	ans_k = 0
	ir = 0
	for il in range(0, len(v) - 1):
		l = v[il]
		while ir < len(v) and v[ir] - l <= K - 1:
			ir += 1
		ans_k += ir - 1 - il
	ans += ans_k
print(ans)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
current = [0]
dic = {}
dic[0] = 1
ans = 0
for i in range(n):
	current.append((current[-1] + a[i] - 1) % k)
	if i >= k - 1:
		dic[current[-k - 1]] -= 1
	if current[-1] in dic:
		ans += dic[current[-1]]
		dic[current[-1]] += 1
	else:
		dic[current[-1]] = 1
print(ans)


(N, K) = map(int, input().split())
a = list(map(int, input().split()))
A = [0]
for i in range(N):
	A.append(A[-1] + a[i] - 1)
for i in range(len(A)):
	A[i] %= K
D = {}
D[0] = 1
ans = 0
for i in range(1, N + 1):
	if A[i] in D:
		ans += D[A[i]]
		D[A[i]] += 1
	else:
		D[A[i]] = 1
	if i - K + 1 >= 0:
		D[A[i - K + 1]] -= 1
if K == 1:
	print(0)
else:
	print(ans)


from itertools import accumulate, chain
from collections import defaultdict
(N, K) = map(int, input().split())
A = accumulate(chain((0,), map(lambda x: int(x) - 1, input().split())))
d = defaultdict(list)
for (i, a) in enumerate(A):
	d[a % K].append(i)
cnt = 0
for l in d.values():
	if len(l) == 1:
		continue
	j = 0
	for (i, li) in enumerate(l):
		li += K
		while j < len(l) and l[j] < li:
			j += 1
		cnt += j - i - 1
print(cnt)


from itertools import accumulate
from collections import Counter
(N, K, *A) = map(int, open(0).read().split())
A = [a - 1 for a in A]
B = [0] + [b % K for b in accumulate(A)]
if K > N:
	Cnt = Counter(B)
	ans = sum((v * (v - 1) // 2 for v in Cnt.values()))
else:
	Cnt = Counter(B[:K])
	ans = sum((v * (v - 1) // 2 for v in Cnt.values()))
	for i in range(N + 1 - K):
		Cnt[B[i]] -= 1
		ans += Cnt[B[i + K]]
		Cnt[B[i + K]] += 1
print(ans)


(n, k) = map(int, input().split())
a = [0] + list(map(int, input().split()))
for i in range(n):
	a[i + 1] = (a[i + 1] + a[i] - 1) % k
from collections import defaultdict
d = defaultdict(int)
x = 0
d[0] = 1
for i in range(1, n + 1):
	if i - k >= 0:
		d[a[i - k]] -= 1
	x += d[a[i]]
	d[a[i]] += 1
print(x)


from itertools import accumulate
from collections import defaultdict, deque

def resolve():
	(N, K) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	A = accumulate([a % K for a in A])
	A = [0] + list(A)
	cnt = defaultdict(int)
	q = deque()
	ans = 0
	for r in range(N + 1):
		t = (A[r] - r) % K
		ans += cnt[t]
		cnt[t] += 1
		q.append(t)
		if len(q) == K:
			left = q.popleft()
			cnt[left] -= 1
	print(ans)

def __starting_point():
	resolve()
__starting_point()


from collections import Counter

def solve():
	ans = 0
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	cum = [0] * (N + 1)
	for i in range(N):
		cum[i + 1] = (cum[i] + A[i]) % K
	for i in range(N):
		cum[i + 1] = (i + 1 - cum[i + 1]) % K
	if N < K:
		c = Counter(cum)
		for v in c.values():
			ans += v * (v - 1) // 2
	else:
		c = Counter(cum[:K - 1])
		for i in range(N):
			c[cum[i]] -= 1
			if i + K - 1 <= N:
				c[cum[i + K - 1]] += 1
			ans += c[cum[i]]
	return ans
print(solve())


from collections import defaultdict
import numpy as np
(n, k) = map(int, input().split())
a = [0] + list(np.cumsum(list(map(int, input().split()))))
dic = defaultdict(int)
c = 0
for i in range(len(a)):
	p = (a[i] - i) % k
	c += dic[p]
	dic[p] += 1
	if i >= k - 1:
		dic[(a[i - k + 1] - (i - k + 1)) % k] -= 1
print(c)


from collections import defaultdict as dd
(N, K) = map(int, input().split())
a = list(map(int, input().split()))
b = [val - 1 for val in a]
c = [0] * (N + 1)
for (i, val) in enumerate(a):
	c[i + 1] = (c[i] + val - 1) % K
dic = dd(int)
K2 = min(N, K - 1)
right = K2
for (k, val) in enumerate(c[1:K2 + 1]):
	dic[val] += 1
res = 0
prev = 0
for val in c[1:]:
	tgt = prev
	res += dic[tgt]
	if right != N:
		right += 1
		dic[c[right]] += 1
	dic[val] = max(0, dic[val] - 1)
	prev = val
print(res)


from collections import defaultdict
(n, k) = list(map(int, input().split()))
A = list(map(int, input().split()))
accm = [0] * (n + 1)
for i in range(n):
	accm[i + 1] = accm[i] + A[i]
li = [(val - itr) % k for (itr, val) in enumerate(accm)]
ans = 0
box = defaultdict(int)
for i in range(n + 1):
	if i >= k:
		box[li[i - k]] -= 1
	ans += box[li[i]]
	box[li[i]] += 1
print(ans)


(n, k) = map(int, input().split())
a = [int(i) for i in input().split()]
ans = 0
dp = dict()
dp[0] = 1
pref = [0 for i in range(n + 1)]
pre = 0
for i in range(n):
	pre += a[i] - 1
	pre %= k
	pref[i + 1] = pre
	if i >= k - 1:
		dp[pref[i - k + 1]] -= 1
	try:
		ans += dp[pre]
		dp[pre] += 1
	except:
		dp[pre] = 1
print(ans)


import collections
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
m = [0]
for i in range(n):
	m.append(m[-1] + a[i])
for i in range(n + 1):
	m[i] -= i
	m[i] %= k
ans = 0
dict = collections.defaultdict(int)
for i in range(1, n + 1):
	x = m[i]
	if i <= k - 1:
		dict[m[i - 1]] += 1
	else:
		dict[m[i - 1]] += 1
		dict[m[i - k]] -= 1
	ans += dict[x]
print(ans)


(N, K) = map(int, input().split())
A = list(map(int, input().split()))
for i in range(N):
	A[i] -= 1
	A[i] %= K
hm = {}
hm[A[0]] = 1
out = 0
for i in range(1, N):
	A[i] += A[i - 1]
	A[i] %= K
for i in range(min(K - 1, N)):
	if A[i] == 0 and K != 1:
		out += 1
for i in range(1, min(N, K)):
	if A[i] in hm:
		hm[A[i]] += 1
	else:
		hm[A[i]] = 1
	out += hm[A[i]] - 1
for i in range(min(K, N), N):
	if A[i] in hm:
		hm[A[i]] += 1
	else:
		hm[A[i]] = 1
	hm[A[i - K]] -= 1
	out += hm[A[i]] - 1
print(int(out))


import bisect
(n, k) = map(int, input().split())
a = [0] + list(map(int, input().split()))
for i in range(n):
	a[i + 1] += a[i]
ans = 0
for i in range(n):
	a[i + 1] -= i + 1
	a[i + 1] %= k
d = dict()
for (i, x) in enumerate(a):
	if x in d:
		d[x].append(i)
	else:
		d[x] = [i]
ans = 0
for v in d.values():
	for (i, x) in enumerate(v):
		t = bisect.bisect_right(v, x + k - 1) - i - 1
		ans += t
print(ans)


(n, k) = map(int, input().split())
m = list(map(int, input().split()))
T = [0] * (n + 1)
b = 0
for (i, a) in enumerate(m):
	b += a - 1
	b %= k
	T[i + 1] = b
tmp = {}
count = 0
for (i, b) in enumerate(T):
	if i >= k:
		tmp[T[i - k]] -= 1
	if b in tmp:
		count += tmp[b]
		tmp[b] += 1
	else:
		tmp[b] = 1
print(count)


from collections import defaultdict
from itertools import accumulate
import bisect
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
s = list(accumulate([0] + a))
b = [s[i] - i for i in range(n + 1)]
d = defaultdict(list)
for i in range(n + 1):
	d[b[i] % k].append(i)
ans = 0
for x in d.keys():
	l = d[x]
	for j in range(len(l)):
		y = l[j]
		ans += max(0, bisect.bisect_right(l, k + y - 1) - j - 1)
print(ans)


from collections import defaultdict, deque
(n, k) = map(int, input().split())
a = tuple(map(int, input().split()))
acc = [0]
t = 0
for a_ in a:
	t = (t + a_ - 1) % k
	acc.append(t)
d = defaultdict(int)
ret = 0
count = 0
dq = deque()
for acc_ in acc:
	ret += d[acc_]
	d[acc_] += 1
	dq.append(acc_)
	if len(dq) >= k:
		v = dq.popleft()
		d[v] -= 1
print(ret)


import sys
from itertools import accumulate
from collections import defaultdict
input = sys.stdin.readline
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a = [i - 1 for i in a]
suma = [0] + list(accumulate(a))
suma = [i % k for i in suma]
rem = defaultdict(int)
ans = 0
if k > n:
	for i in range(n + 1):
		x = suma[i]
		rem[x] += 1
	for s in rem.values():
		ans += s * (s - 1) // 2
	print(ans)
	return
for i in range(k):
	x = suma[i]
	rem[x] += 1
for s in rem.values():
	ans += s * (s - 1) // 2
for i in range(n - k + 1):
	rem[suma[i] % k] -= 1
	rem[suma[i + k] % k] += 1
	ans += rem[suma[i + k]] - 1
print(ans)


MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1, 0, 1, 0)
dx = (0, 1, 0, -1)

def main():
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	cum = [0] * (n + 1)
	dic = {0: 1}
	ans = 0
	for i in range(min(n, k - 1)):
		cum[i + 1] = (cum[i] + a[i]) % k
		tmp = (cum[i + 1] - i - 1) % k
		if tmp in dic:
			dic[tmp] += 1
		else:
			dic[tmp] = 1
	for v in list(dic.values()):
		ans += v * (v - 1) // 2
	for i in range(max(n - k + 1, 0)):
		dic[(cum[i] - i) % k] -= 1
		cum[i + k] = (cum[i + k - 1] + a[i + k - 1]) % k
		tmp = (cum[i + k] - i - k) % k
		if tmp in dic:
			ans += dic[tmp]
			dic[tmp] += 1
		else:
			dic[tmp] = 1
	print(ans)

def __starting_point():
	main()
__starting_point()


import collections
(N, K) = list(map(int, input().split()))
A = list(map(int, input().split()))
table = collections.defaultdict(int)
ans = 0
s = [0] * (N + 1)
a = set()
for i in range(N):
	s[i + 1] = s[i] + A[i]
s = [(s[i] - i) % K for i in range(N + 1)]
for i in range(N + 1):
	ans += table[s[i]]
	table[s[i]] += 1
	if i >= K - 1:
		table[s[i - K + 1]] -= 1
print(ans)


import numpy as np
from collections import defaultdict
(N, K) = list(map(int, input().split()))
As = np.array([0] + list(map(int, input().split())))
mods = As % K
csum_mods = np.cumsum(mods)
magic_array = (csum_mods - np.arange(0, N + 1)) % K
indices = defaultdict(list)
for (i, m) in enumerate(magic_array.tolist()):
	indices[m].append(i)
ans = 0
for ls in list(indices.values()):
	j = 1
	for i in range(len(ls)):
		while j < len(ls):
			if ls[j] - ls[i] < K:
				j += 1
			else:
				break
		ans += j - i - 1
print(ans)


import sys, queue, math, copy, itertools, bisect, collections, heapq

def main():
	LI = lambda : [int(x) for x in sys.stdin.readline().split()]
	(N, K) = LI()
	A = LI()
	c = 0
	d = collections.Counter()
	d[0] = 1
	ans = 0
	r = [0] * (N + 1)
	for (i, x) in enumerate(A):
		if i >= K - 1:
			d[r[i - (K - 1)]] -= 1
		c = (c + x - 1) % K
		ans += d[c]
		d[c] += 1
		r[i + 1] = c
	print(ans)
main()


(N, K) = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
s = [0] * (N + 1)
for i in range(N):
	s[i + 1] = s[i] + A[i]
	s[i + 1] %= K
s.reverse()
for i in range(N + 1):
	s[i] += i % K
	s[i] %= K
d = {}
ans = 0
for i in range(N + 1):
	if s[i] not in d:
		d[s[i]] = 0
	if i >= K:
		d[s[i - K]] -= 1
	ans += d[s[i]]
	d[s[i]] += 1
print(ans)


(N, K) = map(int, input().split())
A = list(map(int, input().split()))
B = [0] * (N + 1)
for i in range(N):
	B[i + 1] = (B[i] + A[i] - 1) % K
r = 0
from collections import defaultdict
d = defaultdict(int)
for i in range(N + 1):
	r += d[B[i]]
	d[B[i]] += 1
	if K - 1 <= i:
		d[B[i - K + 1]] -= 1
print(r)


import sys
from collections import defaultdict
import bisect
sys.setrecursionlimit(10 ** 9)
(N, K) = map(int, input().split())
A = list(map(lambda x: int(x) - 1, input().split()))
S = [0] * (N + 1)
R = defaultdict(list)
R[0].append(0)
for i in range(N):
	S[i + 1] = (S[i] + A[i]) % K
	R[S[i + 1]].append(i + 1)
ans = 0
for i in range(N + 1):
	a = bisect.bisect_right(R[S[i]], i)
	b = bisect.bisect_left(R[S[i]], i + K)
	ans += b - a
print(ans)


(n, k) = map(int, input().split())
al = list(map(int, input().split()))
import itertools
al_ac = [0] + list(itertools.accumulate(al))
for i in range(n + 1):
	al_ac[i] = (al_ac[i] - i) % k
from collections import defaultdict
dic = defaultdict(int)
ans = 0
for i in range(n + 1):
	ans += dic[al_ac[i]]
	dic[al_ac[i]] += 1
	if i - k + 1 >= 0:
		dic[al_ac[i - k + 1]] -= 1
print(ans)


def main():
	(n, k) = map(int, input().split())
	b = list(map(int, input().split()))
	a = [0] * (n + 1)
	for i in range(n):
		a[i + 1] = b[i]
	for i in range(n + 1):
		if 0 < i:
			a[i] += a[i - 1]
		a[i] %= k
	for i in range(1, n + 1):
		a[i] = (a[i] - i % k + k) % k
	dic = {}
	ans = 0
	(l, r) = (0, 0)
	while r < n + 1:
		x = a[r]
		if k <= r - l:
			dic[a[l]] -= 1
			l += 1
		if x in dic.keys():
			ans += dic[x]
			dic[x] += 1
		else:
			dic[x] = 1
		r += 1
	print(ans)

def __starting_point():
	main()
__starting_point()


from collections import defaultdict
import bisect
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
s = 0
S = [0]
for (i, a) in enumerate(A):
	s += a
	S.append(s % K)
cnt = 0
dic = {}
for (i, s) in enumerate(S):
	x = (s - i) % K
	if x in dic:
		cnt += dic[x]
		dic[x] += 1
	else:
		dic[x] = 1
	K_prev = i - K + 1
	if K_prev >= 0:
		y = (S[K_prev] - K_prev) % K
		dic[y] -= 1
print(cnt)


import sys
from itertools import accumulate
from collections import Counter
INF = float('inf')

def solve(N: int, K: int, A: 'List[int]'):
	ans = 0
	acc = [0] + list(accumulate(A))
	cnt = Counter()
	for j in range(1, N + 1):
		if j - 1 >= 0:
			cnt[(acc[j - 1] - (j - 1)) % K] += 1
		if j - K >= 0:
			cnt[(acc[j - K] - (j - K)) % K] -= 1
		ans += cnt[(acc[j] - j) % K]
	print(ans)
	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))
	K = int(next(tokens))
	A = [int(next(tokens)) for _ in range(N)]
	solve(N, K, A)

def __starting_point():
	main()
__starting_point()


(n, k) = map(int, input().split())
l = list(map(int, input().split()))
l = [c - 1 for c in l]
l = [0] + l
from itertools import accumulate
cum = list(accumulate(l))
cum = [c % k for c in cum]
from collections import deque
ans = 0
d = {}
q = deque()
for i in range(n + 1):
	if cum[i] not in d:
		d[cum[i]] = 1
	else:
		ans += d[cum[i]]
		d[cum[i]] += 1
	q.append(cum[i])
	if len(q) == k:
		rem = q.popleft()
		d[rem] -= 1
print(ans)


from collections import Counter
(N, K) = list(map(int, input().split()))
A = list(map(int, input().split()))
S = [0] * (N + 1)
for i in range(N):
	S[i + 1] = S[i] + A[i]
cnt = 0
C = Counter()
for r in range(N + 1):
	R = (S[r] - r) % K
	cnt += C[R]
	C[R] += 1
	l = r - (K - 1)
	if l >= 0:
		L = (S[l] - l) % K
		C[L] -= 1
print(cnt)


(n, k) = list(map(int, input().split()))
l = list(map(int, input().split()))
mo = [0]
mod = [0]
for i in range(n):
	a = l[i] % k
	mo.append((a + mo[-1]) % k)
	mod.append((mo[-1] - (i + 1)) % k)
dic = {0: 1}
le = 1
ans = 0
for i in range(1, n + 1):
	if le < k:
		if mod[i] in dic:
			ans += dic[mod[i]]
			dic[mod[i]] += 1
		else:
			dic[mod[i]] = 1
		le += 1
	else:
		dic[mod[i - k]] -= 1
		if mod[i] in dic:
			ans += dic[mod[i]]
			dic[mod[i]] += 1
		else:
			dic[mod[i]] = 1
print(ans)


(N, K) = map(int, input().split())
A = [0] + list(map(int, input().split()))
from bisect import bisect_right as br

def main():
	dic = {}
	for i in range(1, N + 1):
		A[i] += A[i - 1]
	for j in range(N + 1):
		if (A[j] - j) % K in dic:
			dic[(A[j] - j) % K].append(j)
		else:
			dic[(A[j] - j) % K] = [j]
	ans = 0
	for i in range(1, N + 1):
		tmp = dic[(A[i] - i) % K]
		left = br(tmp, i - K)
		right = br(tmp, i) - 1
		ans += right - left
	print(ans)
	return

def __starting_point():
	main()
__starting_point()


from collections import defaultdict
(n, k) = map(int, input().split())
seq = list(map(int, input().split()))
count = defaultdict(int)
count[0] = 1
prefix = [0] * (n + 1)
ans = 0
for i in range(n):
	pre = prefix[i + 1] = (prefix[i] + seq[i] - 1) % k
	if i >= k - 1:
		count[prefix[i - k + 1]] -= 1
	ans += count[pre]
	count[pre] += 1
print(ans)


from collections import defaultdict
from bisect import bisect_left, bisect_right
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a_cs = [0] * (n + 1)
for i in range(n):
	a_cs[i + 1] = a_cs[i] + a[i]
d = defaultdict(list)
for i in range(n + 1):
	d[(a_cs[i] - i) % k].append(i)
ans = 0
for l in range(n):
	idx_1 = bisect_right(d[(a_cs[l] - l) % k], l)
	idx_2 = bisect_left(d[(a_cs[l] - l) % k], l + k)
	ans += idx_2 - idx_1
print(ans)


from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 5)
(N, K) = map(int, input().split())
A = [int(i) for i in input().split()]
s = [0]
for i in range(N):
	s.append((s[-1] + A[i]) % K)
for i in range(N + 1):
	s[i] = (s[i] - i) % K
d = defaultdict(int)
ret = 0
for i in range(min(K, N + 1)):
	ret += d[s[i]]
	d[s[i]] += 1
for i in range(K, N + 1):
	d[s[i - K]] -= 1
	ret += d[s[i]]
	d[s[i]] += 1
print(ret)


from collections import defaultdict
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
ruisekiwa = [0 for _ in range(n + 1)]
for i in range(n):
	ruisekiwa[i + 1] = (ruisekiwa[i] + a[i] - 1) % k
dp = defaultdict(lambda : 0)
ans = 0
tmp = 0
for i in range(n + 1):
	tmp += 1
	if tmp > k:
		dp[ruisekiwa[i - k]] -= 1
	ans += dp[ruisekiwa[i]]
	dp[ruisekiwa[i]] += 1
print(ans)


def solve():
	from itertools import accumulate
	from sys import stdin
	f_i = stdin
	(N, K) = map(int, f_i.readline().split())
	A = map(int, f_i.readline().split())
	S = accumulate((a - 1 for a in A))
	S = (0,) + tuple((s % K for s in S))
	rec = {}
	ans = 0
	for (j, S_j) in enumerate(S):
		if j >= K:
			rec[S[j - K]] -= 1
		if S_j in rec:
			ans += rec[S_j]
			rec[S_j] += 1
		else:
			rec[S_j] = 1
	print(ans)
solve()


(N, K) = [int(n) for n in input().split()]
A = [int(n) for n in input().split()]
count = 0
for i in range(1, N + 1):
	A[i - 1] = A[i - 1] - 1
check = {0: [0, 1, [0]]}
s = 0
for i in range(1, N + 1):
	s = (s + A[i - 1]) % K
	if s in check:
		j = check[s][0]
		l = check[s][1]
		while j < l and i - check[s][2][j] >= K:
			j += 1
		check[s][0] = j
		count += l - j
		check[s][2].append(i)
		check[s][1] = l + 1
	else:
		check[s] = [0, 1, [i]]
print(count)


from collections import Counter
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
A = list(map(lambda x: x % K, A))
S = [0 for _ in range(N + 1)]
for i in range(N):
	S[i + 1] = (S[i] + A[i] - 1) % K
ans = 0
C = Counter(S[:K])
for (k, v) in C.items():
	ans += v * (v - 1) // 2
for i in range(K, N + 1):
	deln = S[i - K]
	C[deln] -= 1
	addn = S[i]
	if addn in C:
		ans += C[addn]
		C[addn] += 1
	else:
		C[addn] = 1
print(ans)


from collections import defaultdict
(N, K) = map(int, input().split())
X = list(map(int, input().split()))
cs = [0] * (N + 1)
for i in range(N):
	cs[i + 1] = cs[i] + X[i]
y = [(cs[i] - i) % K for i in range(N + 1)]
ctr = defaultdict(int)
ans = 0
for i in range(N + 1):
	ans += ctr[y[i]]
	ctr[y[i]] += 1
	if i - K + 1 >= 0:
		ctr[y[i - K + 1]] -= 1
print(ans)


(n, k) = map(int, input().split())
A = list(map(int, input().split()))
c = 0
from collections import Counter
d = Counter()
d[0] = 1
ans = 0
r = [0] * (n + 1)
for (i, x) in enumerate(A):
	if i >= k - 1:
		d[r[i - (k - 1)]] -= 1
	c = (c + x - 1) % k
	ans += d[c]
	d[c] += 1
	r[i + 1] = c
print(ans)


from collections import defaultdict
d = defaultdict(int)
(N, K) = map(int, input().split())
A = [0] + list(map(int, input().split()))
S = [None] * (N + 1)
S[0] = 0
cnt = 0
d[0] = 1
for i in range(1, N + 1):
	S[i] = (S[i - 1] + A[i] - 1) % K
for i in range(1, N + 1):
	if i - K >= 0:
		d[S[i - K]] -= 1
	cnt += d[S[i]]
	d[S[i]] += 1
print(cnt)


import sys
from bisect import bisect_left

def solve():
	input = sys.stdin.readline
	(N, K) = map(int, input().split())
	A = [int(a) % K - 1 for a in input().split()]
	sum_A = [0 for _ in range(N + 1)]
	count = 0
	modK = dict()
	modK[0] = [0]
	for i in range(N):
		sum_A[i + 1] = (sum_A[i] + A[i]) % K
		if sum_A[i + 1] not in modK:
			modK[sum_A[i + 1]] = [i + 1]
		else:
			modK[sum_A[i + 1]].append(i + 1)
	for key in modK:
		lenK = len(modK[key])
		for (i, a) in enumerate(modK[key]):
			count += bisect_left(modK[key], a + K, i, lenK) - i - 1
	print(count)
	return 0

def __starting_point():
	solve()
__starting_point()


from collections import defaultdict

def gets():
	return list(map(int, input().split()))
(N, K) = gets()
A = gets()
S = [0] * (N + 1)
for i in range(N):
	S[i + 1] = (S[i] + A[i] - 1) % K
cnt = defaultdict(int)
ans = 0
cnt[0] += 1
for i in range(1, N + 1):
	if i - K >= 0:
		cnt[S[i - K]] -= 1
	ans += cnt[S[i]]
	cnt[S[i]] += 1
print(ans)


def main():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a = [i - 1 for i in a]
	from itertools import accumulate
	import bisect
	a = [0] + list(accumulate(a))
	d = dict()
	a = [i % k for i in a]
	cnt = 0
	for (j, i) in enumerate(a):
		if i not in d.keys():
			d[i] = [j]
		else:
			d[i].append(j)
	for l in d.values():
		for (j, i) in enumerate(l):
			cnt += bisect.bisect_left(l, i + k) - j - 1
	print(cnt)
main()


from collections import defaultdict
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
S = [0]
for i in range(N):
	S.append((S[-1] + A[i] - 1) % K)
D = defaultdict(int)
count = 0
for i in range(N + 1):
	count += D[S[i]]
	D[S[i]] += 1
	if i - K + 1 >= 0:
		D[S[i - K + 1]] -= 1
print(count)


from collections import defaultdict
(N, K) = map(int, input().split())
alist = list(map(int, input().split()))
slist = [0]
for i in range(N):
	slist.append(slist[-1] + alist[i])
sslist = []
for i in range(N + 1):
	sslist.append((slist[i] - i) % K)
answer = 0
si_dic = defaultdict(int)
for i in range(N + 1):
	if i - K >= 0:
		si_dic[sslist[i - K]] -= 1
	answer += si_dic[sslist[i]]
	si_dic[sslist[i]] += 1
print(answer)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
s = [0]
for i in range(len(a)):
	s.append(s[-1] + a[i])
ss = []
for i in range(len(s)):
	ss.append((s[i] - i) % k)
ans = 0
from collections import Counter
c = Counter(ss[1:min(k, len(ss))])
for i in range(len(ss)):
	ans += c[ss[i]]
	if i + 1 < len(ss):
		c[ss[i + 1]] -= 1
	if i + k < len(ss):
		c[ss[i + k]] += 1
print(ans)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a2 = [0]
for i in range(n):
	a2.append(a2[-1] + a[i] - 1)
a2 = [a2[i] % k for i in range(n + 1)]
count = {}
temp = a2[:min(k, len(a2))]
for i in temp:
	count.setdefault(i, 0)
	count[i] += 1
ans = 0
for i in count.values():
	ans += i * (i - 1) // 2
for i in range(1, len(a2) - len(temp) + 1):
	temp = a2[i:i + len(temp)]
	temp2 = temp[:-1]
	ans += temp2.count(temp[-1])
print(ans)


from collections import Counter
from itertools import accumulate
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
d = Counter()
A = [0] + list(accumulate(A))
A = [a % K for a in A]
ans = 0
for i in range(N + 1):
	ans += d[(A[i] - i) % K]
	d[(A[i] - i) % K] += 1
	if i - K + 1 >= 0:
		d[(A[i - K + 1] - (i - K + 1)) % K] -= 1
print(ans)


(N, K) = map(int, input().split())
A = list(map(int, input().split()))
if K == 1:
	print(0)
else:
	(S, LUT, ans) = ([0], {0: 1}, 0)
	for a in A:
		S.append(S[-1] + a)
	for i in range(1, N + 1):
		p = (S[i] - i) % K
		ans += LUT.get(p, 0)
		LUT[p] = LUT.get(p, 0) + 1
		if i - K + 1 >= 0:
			LUT[(S[i - K + 1] - i + K - 1) % K] -= 1
	print(ans)


(N, K) = map(int, input().split())
A = list(map(int, input().split()))
X = [0 for _ in range(N)]
D = {0: [-1]}
E = {0: 1}
X[0] = (A[0] - 1) % K
if X[0] in D:
	D[X[0]].append(0)
	E[X[0]] += 1
else:
	D[X[0]] = [0]
	E[X[0]] = 1
for i in range(1, N):
	X[i] = (X[i - 1] + A[i] - 1) % K
	if X[i] in D:
		D[X[i]].append(i)
		E[X[i]] += 1
	else:
		D[X[i]] = [i]
		E[X[i]] = 1
S = 0
for i in D:
	n = E[i]
	if n > 1:
		L = D[i][:]
		m = L[-1]
		for j in range(n - 1):
			x = L[j]
			if m - x < K:
				S += n - 1 - j
			else:
				(l, r) = (j, n)
				d = (l + r) // 2
				tmp = 2 * n
				while tmp != 0:
					if L[d] - x <= K - 1:
						l = d
						d = (l + r) // 2
					else:
						r = d
						d = (l + r) // 2
					tmp //= 2
				S += d - j
print(S)


from collections import defaultdict as d
from itertools import accumulate as ac
(n, k) = map(int, input().split())
a = [0] + list(ac(list(map(int, input().split()))))
b = d(int)
c = 0
for i in range(n + 1):
	p = (a[i] - i) % k
	c += b[p]
	b[p] += 1
	if i - k + 1 >= 0:
		b[(a[i - k + 1] - i + k - 1) % k] -= 1
print(c)


import sys
import numpy as np
from collections import defaultdict
sr = lambda : sys.stdin.readline().rstrip()
ir = lambda : int(sr())
lr = lambda : list(map(int, sr().split()))
(N, K) = lr()
A = np.array([1] + lr())
A = (A - 1) % K
N += 1
Acum = (A.cumsum() % K).tolist()
answer = 0
dic = defaultdict(int)
for (i, cur) in enumerate(Acum):
	answer += dic[cur]
	dic[cur] += 1
	if i >= K - 1:
		vanish = Acum[i - (K - 1)]
		dic[vanish] -= 1
print(answer)


(N, K) = map(int, input().split())
A = list(map(int, input().split()))
S = [0] * (N + 1)
S2 = [0] * (N + 1)
dict = {}
for i in range(N):
	S[i + 1] = S[i] + A[i]
	S2[i + 1] = (S[i + 1] - i - 1) % K
ans = 0
for i in range(N + 1):
	if dict.get(S2[i], 0):
		ans += dict[S2[i]]
	dict[S2[i]] = dict.get(S2[i], 0) + 1
	if i >= K - 1:
		dict[S2[i - (K - 1)]] -= 1
print(ans)


from collections import defaultdict
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
S = [0] * (N + 1)
T = [0] * (N + 1)
for i in range(N):
	S[i + 1] = (S[i] + A[i]) % K
	T[i + 1] = (S[i + 1] - (i + 1)) % K
rest = defaultdict(int)
for i in range(N + 1):
	if i < K:
		ans += rest[T[i]]
		rest[T[i]] += 1
	else:
		rest[T[i - K]] -= 1
		ans += rest[T[i]]
		rest[T[i]] += 1
print(ans)


from collections import Counter
(N, K) = list(map(int, input().split()))
A = list(map(int, input().split()))
ans = 0
c = Counter()
c[0] = 1
S = [0] * (N + 1)
s = 0
for (idx, a) in enumerate(A):
	idx += 1
	if idx >= K:
		c[S[idx - K]] -= 1
	s = (s + a) % K
	b = (s - idx) % K
	S[idx] = b
	ans += c[b]
	c[b] += 1
print(ans)


from collections import defaultdict

def cnt_func(X):
	res = 0
	right = 0
	L = len(X)
	for i in range(L):
		while right + 1 < L and X[right + 1] < K + X[i]:
			right += 1
		res += right - i
	return res
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
A.insert(0, 0)
for i in range(1, N + 1):
	A[i] += A[i - 1]
B = [0 for i in range(N + 1)]
for i in range(N + 1):
	B[i] = (A[i] - i) % K
ans = 0
Mod = defaultdict(list)
for i in range(N + 1):
	Mod[B[i]].append(i)
for X in Mod.values():
	ans += cnt_func(X)
print(ans)


from collections import defaultdict
(n, k) = list(map(int, input().split()))
A = list(map(int, input().split()))
ans = 0
shukei = defaultdict(int)
S = [0] * (n + 1)
T = [0] * (n + 1)
for i in range(1, n + 1):
	S[i] = S[i - 1] + A[i - 1]
	S[i] %= k
	T[i] = S[i] - i
	T[i] %= k
ans = 0
if k > n + 1:
	for i in range(n + 1):
		shukei[T[i]] += 1
	for (key, num) in list(shukei.items()):
		ans += num * (num - 1) // 2
else:
	shukei = defaultdict(int)
	for i in range(k):
		shukei[T[i]] += 1
	for (key, num) in list(shukei.items()):
		ans += num * (num - 1) // 2
	for i in range(k, n + 1):
		j = i - k
		shukei[T[j]] -= 1
		temp = T[i]
		num = shukei[temp]
		ans += num
		shukei[temp] += 1
print(ans)


from collections import defaultdict, deque
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
cumA = [0] * (N + 1)
for i in range(1, N + 1):
	cumA[i] = cumA[i - 1] + A[i - 1]
cnt = defaultdict(int)
que = deque([])
ans = 0
for (i, c) in enumerate(cumA):
	while que and que[0][0] <= i - K:
		cnt[que.popleft()[1]] -= 1
	diff = (i - c) % K
	ans += cnt[diff]
	cnt[diff] += 1
	que.append((i, diff))
print(ans)


from itertools import *
from collections import defaultdict

def ints():
	return [int(x) for x in input().split()]

def readi():
	return int(input())
(N, K) = ints()
A = ints()
S = [0] + list(accumulate(A))

def f(i):
	return (S[i] - i) % K
s = 0
memo = defaultdict(int)
for j in range(1, N + 1):
	fj = f(j)
	if j - K >= 0:
		memo[f(j - K)] -= 1
	memo[f(j - 1)] += 1
	s += memo[fj]
print(s)


from collections import deque
(n, k) = map(int, input().split())
a = [int(i) - 1 for i in input().split()]
total = 0
s = [0] * (n + 1)
for i in range(n):
	total += a[i]
	s[i + 1] = total % k
queue = deque()
mp = {}
ans = 0
for j in range(n + 1):
	rem = s[j]
	queue.append(rem)
	if rem in mp:
		ans += mp[rem]
		mp[rem] += 1
	else:
		mp[rem] = 1
	if len(queue) == k:
		mp[queue.popleft()] -= 1
print(ans)


from itertools import accumulate
from collections import defaultdict
(N, K) = map(int, input().split())
Xs = list(accumulate([0] + [int(x) for x in input().split()]))
Xs = [(x - i) % K for (i, x) in enumerate(Xs)]
(d, r) = (defaultdict(int), 0)
for (i, x) in enumerate(Xs):
	d[x] += 1
	if i >= K:
		d[Xs[i - K]] -= 1
	r += d[x] - 1
print(r)


import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappush, heappop
import itertools
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)
(N, K) = list(map(int, input().split()))
A = list(map(int, input().split()))
A = [0] + A
A = list(itertools.accumulate(A))
A = [x % K for x in A]
cnt = defaultdict(int)
ans = 0
for (i, a) in enumerate(A):
	x = (a - i) % K
	ans += cnt[x]
	cnt[x] += 1
	if i >= K - 1:
		y = (A[i - K + 1] - (i - K + 1)) % K
		cnt[y] -= 1
print(ans)


from collections import Counter
(N, K) = map(int, input().split())
A = list(map(lambda s: int(s) % K, input().split()))
cumAm1 = [1] + A
for i in range(1, N + 1):
	cumAm1[i] = (-1 + cumAm1[i - 1] + cumAm1[i]) % K
counts = Counter()
ans = 0
for i in range(N + 1):
	if i >= K:
		counts[cumAm1[i - K]] -= 1
	cur = cumAm1[i]
	ans += counts[cur]
	counts[cur] += 1
print(ans)


import sys
from itertools import accumulate
from collections import defaultdict
input = sys.stdin.readline
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
S_ = list(map(lambda t: (t[1] - t[0]) % K, enumerate(accumulate([0] + A))))
count = 0
C = defaultdict(int)
for t in range(1, N + 1):
	C[S_[t - 1]] += 1
	if t - K >= 0:
		C[S_[t - K]] -= 1
	count += C[S_[t]]
print(count)


(N, K) = map(int, input().split())
A = list(map(int, input().split()))
A = [(a - 1) % K for a in A]
S = [0 for i in range(N + 1)]
for i in range(1, N + 1):
	S[i] = (S[i - 1] + A[i - 1]) % K
kinds = set(S)
counts = {}
ans = 0
for k in kinds:
	counts[k] = 0
for i in range(N + 1):
	counts[S[i]] += 1
	if i >= K:
		counts[S[i - K]] -= 1
	ans += counts[S[i]] - 1
print(ans)


def add(x):
	if x in dic:
		dic[x] += 1
	else:
		dic[x] = 1
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = [0]
for i in range(n):
	b.append((b[-1] + a[i] - 1) % k)
dic = {}
ans = 0
for i in range(n + 1):
	add(b[i])
	ans += dic[b[i]] - 1
	if i - k + 1 >= 0:
		dic[b[i - k + 1]] -= 1
print(ans)


from collections import defaultdict
(n, k) = map(int, input().split())
s = [0] + list(map(int, input().split()))
for i in range(n):
	s[i + 1] += s[i]
dic = defaultdict(int)
ans = 0
for i in range(n + 1):
	x = (s[i] - i) % k
	ans += dic[x]
	dic[x] += 1
	if i >= k - 1:
		y = (s[i - k + 1] - (i - k + 1)) % k
		dic[y] -= 1
print(ans)


import sys
from collections import defaultdict as dd
from bisect import bisect_left as bl
input = sys.stdin.readline
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
res = 0
cs = [0] * (N + 1)
d = dd(list)
d[0].append(0)
for i in range(N):
	cs[i + 1] = cs[i] + A[i] - 1
	cs[i + 1] %= K
	d[cs[i + 1]].append(i + 1)
for i in range(N):
	x = bl(d[cs[i]], i) + 1
	y = bl(d[cs[i]], i + K)
	res += y - x
print(res)


from collections import defaultdict
(n, k) = map(int, input().split())
A = list(map(int, input().split()))
delta_count = defaultdict(int)
sum = [0]
delta_count[0] += 1
for i in range(n):
	sum.append(sum[i] + A[i])
ans = 0
for i in range(1, min(n + 1, k)):
	x = (sum[i] - i) % k
	ans += delta_count[x]
	delta_count[x] += 1
for i in range(min(n + 1, k), n + 1):
	delta_count[(sum[i - k] - i - k) % k] -= 1
	x = (sum[i] - i) % k
	ans += delta_count[x]
	delta_count[x] += 1
print(ans)


(n, k) = map(int, input().split())
a = [0] + list(map(int, input().split()))
for i in range(1, n + 1):
	a[i] += a[i - 1]
for i in range(1, n + 1):
	a[i] = (a[i] - i) % k
b = [[] for i in range(n + 1)]
for i in range(n + 1):
	b[i] = [a[i], i]
b.sort()
left = 0
right = 0
ans = 0
while left < n:
	while right < n:
		if b[left][0] == b[right + 1][0] and b[right + 1][1] - b[left][1] < k:
			right += 1
		else:
			break
	ans += right - left
	left += 1
print(ans)


from collections import defaultdict
from bisect import bisect_left
(n, k) = map(int, input().split())
a = [0] + list(map(int, input().split()))
for i in range(1, n + 1):
	a[i] -= 1
for i in range(n):
	a[i + 1] += a[i]
	a[i] %= k
a[i + 1] %= k
c = defaultdict(list)
for i in range(n + 1):
	c[a[i]].append(i)
ans = 0
for v in c.values():
	for i in range(len(v)):
		ans += bisect_left(v, v[i] + k) - i - 1
print(ans)


from bisect import bisect_left
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
	a[i] -= 1
sm = 0
a_sm = [0]
for i in range(n):
	sm += a[i]
	sm %= k
	a_sm.append(sm)
dic = {}
for i in range(n + 1):
	if a_sm[i] in dic:
		dic[a_sm[i]].append(i)
	else:
		dic[a_sm[i]] = [i]
for t in dic:
	for j in range(len(dic[t]) - 1):
		dm = bisect_left(dic[t], dic[t][j] + k)
		ans += dm - j - 1
print(ans)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a[0] = (a[0] - 1) % k
for i in range(1, n):
	a[i] = (a[i] + a[i - 1] - 1) % k
ans = 0
b = {0: 1}
for i in range(n):
	if i > 0:
		b[a[i - 1]] = b.get(a[i - 1], 0) + 1
	if i >= k:
		b[a[i - k]] -= 1
	if i == k - 1:
		b[0] -= 1
	ans += b.get(a[i], 0)
print(ans)


import sys
from collections import defaultdict
stdin = sys.stdin
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
ns = lambda : stdin.readline().rstrip()
(n, k) = na()
a = na()
cum = [0] * (n + 1)
for i in range(n):
	cum[i + 1] = (cum[i] + a[i] + k - 1) % k
dic = defaultdict(int)
ans = 0
for i in range(n + 1):
	ans += dic[cum[i]]
	dic[cum[i]] += 1
	if i - (k - 1) >= 0:
		dic[cum[i - (k - 1)]] -= 1
print(ans)