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

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
INF = 10**18
AB = [A, B]

def calc(P):
    ret = 0
    for i, p in enumerate(P):
        for q in P[:i]:
            if q > p:
                ret += 1
    return ret

I = set()
def search(P, prev):
    i = len(P)

    if i == N:
        return calc(P)

    ret = INF

    for j in range(N):
        if j in I:
            continue
        n = AB[(i - j) % 2][j]
        if prev > n:
            continue
        P.append(j)
        I.add(j)
        ret = min(ret, search(P, n))
        I.remove(j)
        P.pop()

    return ret

ans = search([], -10**18)

print(ans if ans != INF else -1)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
AB = (A, B)
INF = 10**18

ans = INF
for state in range(1 << N):
    even = []
    odd = []

    for i in range(N):
        isReverse = (state & (1 << i)) >> i
        val = AB[isReverse][i]

        if i % 2 == 0:
            (even, odd)[isReverse].append((val, i))
        else:
            (odd, even)[isReverse].append((val, i))

    if len(even) != -(-N // 2) or len(odd) != N // 2:
        continue

    even.sort()
    odd.sort()
    odd.append((-1, -1))
    V = []
    P = []
    for (l, i), (r, j) in zip(even, odd):
        V.append(l)
        P.append(i)
        if r >= 0:
            V.append(r)
            P.append(j)

    if not all(l <= r for l, r in zip(V, V[1:])):
        continue

    cnt = 0
    for i, p in enumerate(P):
        for q in P[:i]:
            if p < q:
                cnt += 1
    ans = min(ans, cnt)

print(ans if ans != INF else -1)
### BUGGY CODE ###

def z_al(s):
    le = len(s)
    res = [0 for i in range(le)]
    i, j = 1, 0
    while i < le:
        while i + j < le and s[i + j] == s[j]:
            j += 1
        res[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < le and res[k] + k < j:
            res[i + k] = res[k]
            k += 1
        i += k
        j -= k
    return res
n = int(input())
s = input()
ans = 0
for i in range(n):
    s2 = s[i:]
    res = z_al(s2)
    for j in range(len(s2)):
        ans = max(ans, min(res[j], j))
print(ans)

### FIXED CODE ###

def z_al(s):
    le = len(s)
    res = [0 for i in range(le)]
    i, j = 1, 0
    while i < le:
        while i + j < le and s[i + j] == s[j]:
            j += 1
        res[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < le and res[k] + k < j:
            res[i + k] = res[k]
            k += 1
        i += k
        j -= k
    return res
n = int(input())
s = input()
ans = 0
for i in range(n):
    s2 = s[i:]
    res = z_al(s2)
    for j in range(len(s2)):
        ans = max(ans, min(res[j], j))
print(ans)
### BUGGY CODE ###

import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
 
from functools import reduce
# from math import *
from fractions import *
H, W = map(int, readline().split())
S = [0 for i in range(H)]
for i in range(H):
    S[i] = readline().decode().strip()

from collections import deque
def bfs(start, H, W):
    visited = [False] * (H * W)
    q = deque([])
    q.append((start[0], start[1], 0))
    max_dist = 0
    while q:
        (i, j, dist) = q.popleft()
        max_dist = max(dist, max_dist)
        visited[i * W + j] = True 
        for dy in range(-1, 2):
            for dx in range(-1, 2):
                if dx * dy != 0 or dx == dy:
                    continue
                if i + dy < 0 or i + dy >= H or j + dx < 0 or j + dx >= W:
                    continue
                if S[i + dy][j + dx] == '#':
                    continue
                if visited[(i + dy) * W + j + dx]:
                    continue
                q.append((i + dy, j + dx, dist + 1))
    return max_dist

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        start = (i, j)
        ans = max(ans, bfs(start, H, W))
print(ans)


### FIXED CODE ###

import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
 
from functools import reduce
# from math import *
from fractions import *
H, W = map(int, readline().split())
S = [0 for i in range(H)]
for i in range(H):
    S[i] = readline().decode().strip()

from collections import deque
def bfs(start, H, W):
    INF = 10 ** 9
    dist = [INF] * (H * W)
    q = deque([start])
    dist[start[0] * W + start[1]] = 0
    while q:
        (i, j) = q.popleft()
        d = dist[i * W + j]
        for dy in range(-1, 2):
            for dx in range(-1, 2):
                if dx * dy != 0:
                    continue
                if dx == dy:
                    continue
                if i + dy < 0 or i + dy >= H or j + dx < 0 or j + dx >= W:
                    continue
                if S[i + dy][j + dx] == '#':
                    continue
                if dist[(i + dy) * W + j + dx] != INF:
                    continue
                dist[(i + dy) * W + j + dx] = d + 1
                q.append((i + dy, j + dx))
    return max(x for x in dist if x < INF)

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        start = (i, j)
        ans = max(ans, bfs(start, H, W))
print(ans)
### BUGGY CODE ###

import bisect

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

ans = 0
for mid in B:
    n_bottom = len(C[bisect.bisect_right(C,mid):])
    n_top = len(A[:bisect.bisect_left(A,mid)])
    ans += n_bottom * n_top

print(ans)

### FIXED CODE ###

import bisect

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

ans = 0
for mid in B:
    n_bottom = N - bisect.bisect_right(C,mid)
    n_top = bisect.bisect_left(A,mid)
    ans += n_bottom * n_top

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

import fractions
import functools

MOD = int(1e9) + 7

def lcm(a, b):
    return a // fractions.gcd(a, b) * b

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

v = functools.reduce(lcm, A)
ans = 0
for a in A:
    ans = (ans + v // a) % MOD
print(ans)

### FIXED CODE ###

import fractions
import functools

MOD = int(1e9) + 7


class Inv:

    @classmethod
    def pow(cls, x: int, n: int) -> int:
        ret = 1
        while n > 0:
            if n % 2 == 1:
                ret = ret * x % MOD
            x = x * x % MOD
            n >>= 1
        return ret

    @classmethod
    def inv(cls, x: int) -> int:
        return cls.pow(x % MOD, MOD - 2)


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

MAX_A = 1000010

facts = [0] * MAX_A
p = [False] * MAX_A

def prime():

    for i in range(2, MAX_A):
        p[0] = p[1] = True
        if not p[i]:
            j = 2 * i
            while j < MAX_A:
                p[j] = True
                j += i

prime()

for a in A:
    i = 2
    while i * i <= a:
        if a % i == 0:
            ii = a // i
            c1 = 0
            while a % i == 0:
                c1 += 1
                a //= i
            c2 = 0
            while not p[ii] and a % ii == 0:
                c2 += 1
                a //= ii
            facts[i] = max(facts[i], c1)
            facts[ii] = max(facts[ii], c2)
        i += 1
    if not p[a]:
        facts[a] = max(facts[a], 1)

tar = 1
for idx, c in enumerate(facts):
    if c == 0:
        continue
    tar *= Inv.pow(idx, c)
    tar %= MOD

ans = 0
for a in A:
    ans += tar * Inv.inv(a) % MOD
    ans %= MOD

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

n = int(input())
s = [''.join(sorted(input())) for _ in range(n)]
print(sum(s[i]==s[j] for i in range(n) for j in range(i+1, n)))

### FIXED CODE ###

n = int(input())
s = [''.join(sorted(input())) for _ in range(n)]
ans = 0
d = {}
for i in s:
    if i in d:
        ans += d[i]
        d[i] += 1
    else:
        d[i] = 1
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(str,input().split()))
b = []

for i in range(n):
  b.append(a[i])
  b.reverse()
  
B = ' '.join(b)
print(B)

### FIXED CODE ###

from collections import deque

n = int(input())
a = list(map(str,input().split()))
b = deque()

for i in range(n):
  if i%2== 0:
    b.append(a[i])
  else:
    b.appendleft(a[i])

if len(a)%2 == 0:
  B = ' '.join(b)
  print(B)
else:
  b.reverse()
  B = ' '.join(b)
  print(B)
### BUGGY CODE ###

import queue
n,m = map(int,input().split())
point = 1
now = queue.Queue()
for i in range(n):
    now.put(i)
exist = [1 for i in range(n)]
for turn in range(1,m+1):
    while True:
        a = now.get()
        if exist[a]:
            if exist[(a+turn)%n]:
                print(a+1,(a+turn)%n+1)
                exist[a] = 0
                exist[(a+turn)%n] = 0
                break
            else:
                now.put(a)

### FIXED CODE ###

n,m = map(int,input().split())
if n % 2 == 1:
    ans = [[1+i,n-i] for i in range(n//2)]
else:
    ans = [[1+i,n-i] for i in range(n//4)]+[[n//2+1+i,n//2-1-i] for i in range(n//2-n//4-1)]
for i in range(m):
    print(ans[i][0],ans[i][1])
### BUGGY CODE ###

from collections import *
d=defaultdict(list)
n=int(input())

for s in range(n-1):
    a,b,c=map(int,input().split())
    d[a].append([b,c])
    d[b].append([a,c])

#defaultdict(<class 'list'>, {1: [[2, 1], [3, 1]], 2: [[1, 1], [3, 3]], 3: [[1, 1], [2, 3]]})
 
def DIJKSTRA(point,d):
    cost      = {node:float("inf") for node in d.keys()}
    preference= {node:None         for node in d.keys()}#最適路のこと 
    Q         = set(d.keys())  #頂点のリスト
    cost[point]=0  #開始地点のコストをゼロとする（当たり前
    while True:
        prefnd=min(Q, key=lambda c:cost[c]) #最適な点探し
        Q.remove(prefnd)  #最適だった点を削除
        if len(Q)==0:
            break #全部の点消したら終了
        for p,c in d[prefnd]:  #次の点とそこまでのコスト
            temp=cost[prefnd]+c  #スタートからそこまでのコストを計算
            if temp<cost[p]:   #計算してみたコストがそこに行くまでの最小値ならば
                cost[p]=temp #最小値更新
                preference[p]=prefnd
    return preference,cost  #点のつながりとコスト例 1から１に０ １から２に１ １から３に２

q,k=map(int,input().split())
x,y=DIJKSTRA(k,d)

for i in range(q):
    a,b=map(int,input().split())
    print(y[a]+y[b])


### FIXED CODE ###

from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()

d=defaultdict(list)
n=int(input())

for s in range(n-1):
    a,b,c=map(int,input().split())
    d[a].append([b,c])
    d[b].append([a,c])
#defaultdict(<class 'list'>, {1: [[2, 1], [3, 1]], 2: [[1, 1], [3, 3]], 3: [[1, 1], [2, 3]]})

def DIJKSTRA(point,d):
    cost      = {node:float("inf") for node in d.keys()}
    Q         = []  #頂点のリスト
    cost[point]=0  #開始地点のコストをゼロとする（当たり前
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost

q,k=map(int,input().split())
y=DIJKSTRA(k,d)

for i in range(q):
    a,b=map(int,input().split())
    print(y[a]+y[b])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import numpy as np

def solve(N: int, S: str):
    r = []
    g = []
    b = []

    for i, x in enumerate(S):
        if x ==  "R":r.append(i)
        elif x =="G":g.append(i)
        elif x =="B":b.append(i)

    r = np.array(r)
    g = np.array(g)
    b = np.array(b)


    def rgb(r, g, b):
        sr = set(r)
        sg = set(g)
        sb = set(b)
        ans = 0
        for r_ in r:
            for g_ in g[g>r_]:
                if (g_ + g_ - r_) in sb:
                    ans -= 1
                ans += len(b[b>g_])
        return ans

    k = rgb(r,g,b) + rgb(r,b,g) + rgb(b,g,r) + rgb(b,r,g) + rgb(g,r,b) + rgb(g,b,r)
    print(k)


    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
    S = next(tokens)  # type: str
    solve(N, S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

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

def solve(N: int, S: str):
    r = []
    g = []
    b = []
    rp = 0
    gp = 0
    bp = 0

    rsum = [0]*(N+1)
    bsum = [0]*(N+1)
    gsum = [0]*(N+1)

    for i, x in enumerate(S[::-1]):
        if x ==  "R":
            r.append(i)
            rp = 1
        elif x =="G":
            g.append(i)
            gp = 1
        else:
            b.append(i)
            bp = 1
        rsum[N-1-i] = rsum[N-1-i+1] + rp
        gsum[N-1-i] = gsum[N-1-i+1] + gp
        bsum[N-1-i] = bsum[N-1-i+1] + bp
        rp = 0
        gp = 0
        bp = 0
    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            if S[i] != S[j]:
                if j+j-i<N: k = S[j+j-i]
                else: k = ""
                if (S[i] == "R" and S[j] == "B") or (S[j] == "R" and S[i] == "B"):
                    ans += gsum[j] - (k=="G")*1
                elif (S[i] == "R" and S[j] == "G") or (S[j] == "R" and S[i] == "G"):
                    ans += bsum[j] - (k=="B")*1
                elif (S[i] == "G" and S[j] == "B") or (S[j] == "G" and S[i] == "B"):
                    ans += rsum[j] - (k=="R")*1
    

    print(ans)
  
    return
 
 
# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
    S = next(tokens)  # type: str
    solve(N, S)
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N = int(input())
lsa = list(map(str,input().split()))
lsb = []
for i in range(N):
    if N%2 == 0:
        if i % 2 == 0:
            lsb.append(lsa[i])
        else:
            lsb.insert(0,lsa[i]) 
    if N%2 == 1:
        if i % 2 == 1:
            lsb.append(lsa[i])
        else:
            lsb.insert(0,lsa[i])

print(' '.join(lsb))

### FIXED CODE ###

import collections
N = int(input())
lsa = list(map(str,input().split()))
lsb = collections.deque()
if N%2 == 0:
    for i in range(N):    
        if i % 2 == 0:
            lsb.append(lsa[i])
        else:
            lsb.appendleft(lsa[i])
if N%2 == 1:
    for i in range(N):
        if i % 2 == 1:
            lsb.append(lsa[i])
        else:
            lsb.appendleft(lsa[i])

print(' '.join(lsb))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
yn = ["YES","NO"]
flag = 0
for i in range(n-1):
  for j in range(i+1, n):
    if a[i] == a[j]: 
      flag = 1
print(yn[flag])

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
sa = set(a)
if len(a) == len(sa):
  print("YES")
else:
  print("NO")
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from queue import Queue

def solve():
    n, m = map(int, input().split())
    al = [[int(i) for i in input().split()] for _ in range(n)]

    ans = 0
    q = Queue()
    for i in range(n):
        tq = Queue()
        while not q.empty():
            elem = q.get()
            t = [elem[0] + 1, 
                    [
                        elem[1][0] + al[i][0],
                        elem[1][1] + al[i][1],
                        elem[1][2] + al[i][2]
                        ]
                    ]
            if t[0] == m:
                ans = max(ans, abs(t[1][0]) + abs(t[1][1]) + abs(t[1][2]))
            else:
                tq.put(t)
            tq.put(elem)
        q = tq
        q.put([1, [al[i][0], al[i][1], al[i][2]]])
    print(ans)


if __name__=="__main__":
    solve()


### FIXED CODE ###

n, m = map(int, input().split())
l = [[int(i) for i in input().split()] for _ in [0]*n]
ans = 0

def  getmm(k):
  f = lambda x: (x[0] if k & 1 else -x[0]) + (x[1] if k & 2 else -x[1]) + (x[2] if k & 4 else -x[2])
  al = [f(e) for e in l]
  al.sort(reverse=True)
  return sum(al[:m])

for i in range(8):
  ans = max(ans, getmm(i))
print(ans)
### BUGGY CODE ###

import copy
N = int(input())
L = list(map(int,input().split()))

cnt = 0

for a in L:
    L2 = copy.deepcopy(L)
    L2.remove(a)
    for b in L2:
        L3 = copy.deepcopy(L2)
        L3.remove(b)
        for c in L3:
            if a<b+c and b<c+a and c<a+b:
                cnt+=1
print(cnt//6)

### FIXED CODE ###

import bisect
 
n=int(input())
a=list(map(int,input().split()))
a=sorted(a)
ans=0
for i in range(n-2):
    for j in range(i+1,n-1):
        tmp=a[i]+a[j]
        index=bisect.bisect_left(a,tmp)
        ans+=index-j-1
print(ans)
### BUGGY CODE ###

from collections import defaultdict
n = int(input())
tree = dict()
graph = defaultdict(list)

for i in range(n-1):
    a,b,c = (int(x) for x in input().split())
    tree[a,b] = c
    tree[b,a] = c
    graph[a].append(b)
    graph[b].append(a)

q, k = (int(x) for x in input().split())

dist = dict()
stack = [k,]
visited = [False for _ in range(n+1)]
dist[k] = 0
visited[k] = True
while stack:
    new_stack = []
    for node in stack:
        for next_node in graph[node]:
            if not visited[next_node]:
                visited[next_node]  = True
                dist[next_node] = dist[node] + tree[node, next_node]
                new_stack.extend(graph[node])
    stack = new_stack
for _ in range(q):
    x, y = (int(x) for x in input().split())
    print(dist[x] + dist[y])


### FIXED CODE ###

from collections import defaultdict
n = int(input())
tree = dict()
graph = defaultdict(list)

for i in range(n-1):
    a,b,c = (int(x) for x in input().split())
    tree[a,b] = c
    tree[b,a] = c
    graph[a].append(b)
    graph[b].append(a)

q, k = (int(x) for x in input().split())

dist = dict()
stack = [k,]
visited = [False for _ in range(n+1)]
dist[k] = 0
visited[k] = True

while stack:
    new_stack = []
    for node in stack:
        for next_node in graph[node]:
            if not visited[next_node]:
                visited[next_node]  = True
                dist[next_node] = dist[node] + tree[node, next_node]
                new_stack.append(next_node)
    stack = new_stack

for _ in range(q):
    x, y = (int(x) for x in input().split())
    print(dist[x] + dist[y])
### BUGGY CODE ###

class Combination:
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * \
                modinv[self.mod % i] % self.mod
        return modinv


if __name__ == "__main__":
    N = int(input())
    N += 1
    A = list(map(int, input().split()))
    mod = 10 ** 9 + 7

    comb = Combination(10 ** 5 + 10)
    ans = [comb(N, i) for i in range(1, N + 1)]

    X = max(set(A), key=A.count)
    left = A.index(X)
    right = N - A.index(X, left + 1) - 1
    LR = left + right

    diff = [comb(LR, i) for i in range(LR + 1)]
    for i, d in enumerate(diff):
        ans[i] = (ans[i] - d + mod) % mod

    print(*ans, sep="\n")


### FIXED CODE ###

from collections import Counter

N = int(input())
A = tuple(map(int, input().split()))
mod = 10 ** 9 + 7

U = N + 10
fact = [1] * (U + 1)
inv = [1] * (U + 1)

for i in range(1, U + 1):
    fact[i] = fact[i - 1] * i % mod

inv[U] = pow(fact[i], mod - 2, mod)
for i in range(U, 0, -1):
    inv[i - 1] = inv[i] * i % mod


def comb(N, r):
    if r < 0 or r > N:
        return 0
    res = fact[N] * inv[r] % mod
    res = res * inv[N - r] % mod
    return res


X = Counter(A).most_common()[0][0]
left = A.index(X)
right = A[::-1].index(X)
LR = left + right

for i in range(1, N + 2):
    ans = comb(N+1, i)-comb(LR, i-1)
    ans = (ans + mod) % mod
    print(ans)
### BUGGY CODE ###

import queue

N, X, Y = map(int, input().split())

to = [[] * N for i in range(N)]

for i in range(N-1):
    to[i].append(i+1)
    to[i+1].append(i)

to[X-1].append(Y-1)
to[Y-1].append(X-1)

ans = [0] * N

for i in range(N):
    dis = [0] * N
    dis[i] = 0
    visited = [False] * N
    q = queue.Queue()
    q.put(i)
    visited[i] = True

    while not q.empty():
        tmp_v = q.get()
        for j in to[tmp_v]:
            if not visited[j]:
                dis[j] = dis[tmp_v] + 1
                visited[j] = True
                q.put(j)

    for j in range(N):
        ans[dis[j]] += 1

for i in range(1,N):
    print(ans[i]//2)

### FIXED CODE ###

from collections import deque

N, X, Y = map(int, input().split())

to = [[] * N for i in range(N)]

for i in range(N-1):
    to[i].append(i+1)
    to[i+1].append(i)

to[X-1].append(Y-1)
to[Y-1].append(X-1)

ans = [0] * N

for i in range(N):
    dis = [0] * N
    dis[i] = 0
    visited = [False] * N
    q = deque([])
    q.append(i)
    visited[i] = True

    while len(q) != 0:
        tmp_v = q.popleft()
        for j in to[tmp_v]:
            if not visited[j]:
                dis[j] = dis[tmp_v] + 1
                visited[j] = True
                q.append(j)

    for j in range(N):
        ans[dis[j]] += 1

for i in range(1,N):
    print(ans[i]//2)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())
A=map(lambda a: a%K, A)


S=[0]
for i,a in enumerate(A):
        S.append(S[-1]+a)
  
ans=0

i=0
for i in range(N):
    for k in range(1,K+1):
        if i+k<=N:
            if k==(S[i+k]-S[i])%K:
                ans+=1

print ans


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import defaultdict

N,K=map(int, sys.stdin.readline().split())
if K==1:
    print 0
    quit()
A=map(int, sys.stdin.readline().split())
A=map(lambda a: (a-1)%K, A)

S=[0]
for a in A:
    S.append( (S[-1]+a)%K )   #累積和

d=dict()    #要素：要素の数を持つ

ans=0
for i in range(N+1):
    x=S[i]%K
    if i==0:
        d[x]=1
    else:
        if x in d:
            ans+=d[x]   #自分より前に同じ出現した、自分と同じ要素の数を答えに追加
            d[x]+=1
        else:
            d[x]=1      
        if 0<=i-K+1:
            x_head=S[i-K+1]%K  #長さK-1の範囲で配列Sを見るため、１つ進んだら一番先頭の要素を辞書から削除する
            d[x_head]-=1

print ans