E - Rem of Sum is Num /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 500

問題文

長さ N の正整数列 A_1, A_2, \ldots , A_N と正の整数 K が与えられます。

A の空でない連続する部分列であって、要素の和を K で割った余りが要素の数と等しくなるものの数を求めてください。ただし、2 つの部分列が列として同じでも、取り出す位置が異なるならば区別するものとします。

制約

  • 入力は全て整数である。
  • 1 \leq N \leq 2\times 10^5
  • 1 \leq K \leq 10^9
  • 1 \leq A_i \leq 10^9

入力

入力は以下の形式で標準入力から与えられる。

N K
A_1 A_2 \cdots A_N

出力

条件をみたす部分列の個数を出力してください。


入力例 1

5 4
1 4 2 3 5

出力例 1

4

(1), (4,2), (1,4,2), (5)4 つが条件をみたす部分列です。


入力例 2

8 4
4 2 4 2 4 2 4 2

出力例 2

7

(4,2)4 回、(2,4)3 回数えられています。


入力例 3

10 7
14 15 92 65 35 89 79 32 38 46

出力例 3

8

Score : 500 points

Problem Statement

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 1

5 4
1 4 2 3 5

Sample Output 1

4

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


Sample Input 2

8 4
4 2 4 2 4 2 4 2

Sample Output 2

7

(4,2) is counted four times, and (2,4) is counted three times.


Sample Input 3

10 7
14 15 92 65 35 89 79 32 38 46

Sample Output 3

8