Contest Duration: - (local time) (100 minutes) Back to Home
E - Rem of Sum is Num /

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

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