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).

Difficulty: interview

Starter code:

Solutions:
import bisect
N,K=list(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 collections import Counter


N, K = list(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)


from itertools import accumulate
from collections import defaultdict
import bisect

n,k = list(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)


from itertools import accumulate
from collections import defaultdict

n, k = list(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()))

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 = [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 defaultdict
N, K = list(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
#print(dic)
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('###############')
  print(i,x, ans)
  print(dic)
  print(ldic)
  """
print(ans)


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)


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に答えを格納することにする
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)

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)

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 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=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)

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 collections import defaultdict

N, K = list(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(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
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 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]) % K
    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)


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()))
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)

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


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()))


#01:15
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 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)


N,K=list(map(int,input().split()))
A=list(map(int,input().split()))
for i in range(1,N):
  A[i]+=A[i-1]
  #A[i]=(A[i]+A[i-1]-1)%K

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)


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
    #print(d)
  return print(ans)
def __starting_point():
  main()
__starting_point()

from bisect import *
n,k = list(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 list(sl.keys()):
        sl[s] = []
    sl[s].append(i+1)
ans = 0
for ls in list(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
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 collections import defaultdict
n,k=map(int,input().split())
a=list(map(int,input().split()))
a[0]=(a[0]-1)%k
for i in range(n-1):a[i+1]=(a[i+1]+a[i]-1)%k
d=defaultdict(int)
ans=0
d[0]=1
for i in range(n):
  if i==k-1:d[0]-=1
  if i>=k:d[a[i-k]]-=1
  ans+=d[a[i]]
  d[a[i]]+=1
print(ans)

from collections import Counter
N,K = map(int, input().split())
A = list(map(int, input().split()))
A = list(map(lambda x: x%K, A))

"""
j - i < K and
Sj - Si == j - i (mod K)
Sj - j == Si - i (mod K) この変形が肝だ…
"""

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 = 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)



#!/usr/bin/env python3
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()
    # 各jについて
    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))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)


def __starting_point():
    main()

__starting_point()

#!/usr/bin/env python3
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()

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 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
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([0] + lr())
A = (A-1) % K
Acum = A.cumsum() % K
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)


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 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)

    # 区間 [i,j] の和(累積和): dj+1−di
    # 区間 [i,j] の要素の数(0_indの為 +1): j−i+1
    # 上記を一般化:  dr−dl=r−l となるものの個数を求める
    # r−l<K  の時、mod K において式変形が成り立つ, dr−r=dl−l
    # rを固定し辞書で管理すれば、dl−lと同じ値なので個数を求められる。

    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()

import numpy as np
from collections import defaultdict

N, K = list(map(int, input().split()))
As = np.array([0] + list(map(int, input().split())))
#Find (i, j) that satisfies "sum(As[i:j]) % K == j - i"
#If 0 < j - i < K then 
#sum(As[i:j]) % K == j - i % K
#<-> (sum(As[:j]) - j) % K == (sum(As[:i]) - i) % K

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
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()
d = defaultdict(int)
answer = 0
for i, x in enumerate(Acum):
    answer += d[x]
    d[x] += 1
    if i >= K-1:
        d[Acum[i-(K-1)]] -= 1

print(answer)


n,k=list(map(int,input().split()))
a=list([(int(x)-1)%k for x in 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)


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)




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)

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]
  # print(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)

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]]  # i番目まで取る組み合わせの数
    table[s[i]] += 1
    if i >= K-1:
        # Kで割ったあまりがKを超えることはないので、期限切れのものを引く
        table[s[i-K+1]] -= 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)



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)

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]) % K
    # 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)


# Rem of sum is Num
# Reviewing problem


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)

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)

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()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

__starting_point()

from collections import defaultdict
n,k = list(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 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)


def __starting_point():
    main()

__starting_point()

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)

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)


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
n, k = list(map(int, input().split()))

a = list([int(x) - 1 for x in 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)


import math
import numpy as np
import decimal
import collections
import itertools
import sys
import random
#Union-Find
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
#Prime-Factorize
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
#nCr
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
#拡張Euclidの互除法
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
#BIT
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
#Associative Array
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)
#Floor Sum
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
#Z-Algorithm
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
#mod-sqrt
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)

from collections import defaultdict

n, k = list(map(int, input().split()))
A = list(map(int, input().split()))
ans = 0
shukei = defaultdict(int)
# AiからAjまでの和→SA[j]-SA[i-1]
# SA[j]-SA[i-1]=j-(i-1)
# 今回はkで割ったあまりなのでaccumulateは使わず自力
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
# i>=1, i<jで同じ値になっている組み合わせを探せば良い。
# kで割ったあまりなので、要素数j−(i-1)が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)


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)

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


from collections import defaultdict

def main():
    n, k = list(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)


def __starting_point():
    main()

__starting_point()

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)



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

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()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

__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())

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()))


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)

# dic = {remainder:number}
dic = {0:1}
ans = 0
if n < k:
    for i in range(1, n+1):
        if s[i] in dic:
            ans += dic[s[i]]
            dic[s[i]] += 1
        else:
            dic[s[i]] = 1

else:
    for i in range(1, k):
        if s[i] in dic:
            ans += dic[s[i]]
            dic[s[i]] += 1
        else:
            dic[s[i]] = 1

    for i in range(k, n+1):
        dic[s[i-k]] -= 1
        if s[i] in dic:
            ans += dic[s[i]]
            dic[s[i]] += 1
        else:
            dic[s[i]] = 1

print(ans)

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 = [b%K for b in accumulate(A)]
if K>N:
  Cnt = Counter(B)
  ans = Cnt[0]+sum(v*(v-1)//2 for v in Cnt.values())
else:
  Cnt = Counter(B[:K])
  ans = Cnt[0]+sum(v*(v-1)//2 for v in Cnt.values())
  if B[K-1]==0:
    ans -= 1
  for i in range(N-K):
    Cnt[B[i]] -= 1
    ans += Cnt[B[i+K]]
    Cnt[B[i+K]] += 1
print(ans)

from collections import Counter

N, K = list(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:
            # print("k", t[i-k+2],i-k+2)
            c[t[i-k+1]] -= 1
        r += c[tt]
        c[tt] += 1
        # print("ar", a,tt,r,sorted(c.items()), t)

    return r

print(main())





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()

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()

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
#    print(a)
    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
#        print(l, r)
        r += 1
    print(ans)

def __starting_point():
    main()
__starting_point()

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 = list(map(int, input().split()))
a = list(map(int, input().split()))
d = defaultdict(int)
sa = [0] * (n + 1)
# d[0] = 1
# if k == 1:
#     print(0)
#     return
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)
# from collections import defaultdict
# n, k = map(int, input().split())
# a = list(map(int, input().split()))
# d = defaultdict(int)
# sa = [0] * (n + 1)
# d[0] = 1
# if k == 1:
#     print(0)
#     return
# for i in range(n):
#     sa[i + 1] = sa[i] + a[i]
#     sa[i + 1] %= k
# ans = 0
# for i in range(1, 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)


from collections import defaultdict
n,k = list(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 = {0:1}
ans = 0
for i in range(1,n+1):
    if i < k:
        if mod[i] in dic:
            ans += dic[mod[i]]
            dic[mod[i]] += 1
        else:
            dic[mod[i]] = 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)


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)

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 = 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)

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)

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 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]

    # print(d)

    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(i, si)

    print(ans)


def __starting_point():
    solve()

__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)

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
N,K=map(int,input().split())
alist=list(map(int,input().split()))
#print(alist)

slist=[0]
for i in range(N):
  slist.append(slist[-1]+alist[i])
#print(slist)

sslist=[]
for i in range(N+1):
  sslist.append((slist[i]-i)%K)
#print(sslist)

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 = list(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)


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:
        if x in d:  # inで判定してみる
            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()

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
d = defaultdict(int)
answer = 0
for i, x in enumerate(Acum):
    answer += d[x]
    d[x] += 1
    if i >= K-1:
        d[Acum[i-(K-1)]] -= 1

print(answer)


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)
# 27


import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappush, heappop
import itertools


# read = sys.stdin.read
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
    #print("i", i, "a", a, "x", x, "cnt", cnt)

    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, 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=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)


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
# 累積和が同じになっている箇所に注目、要素がK-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)
# 10