Yura and Developers

题面翻译

有一个长度为$n$的数组$a$，现在要找一个长度至少为$2$的子段。

要求这一子段的和减去最大值，对$k$取余结果为0。 问这样的子段有多少个。

$1≤n≤3*10^5$

$1≤k≤10^6$

$1≤a_i≤10^9$

题目描述

Yura has a team of $k$ developers and a list of $n$ tasks numbered from $1$ to $n$ . Yura is going to choose some tasks to be done this week. Due to strange Looksery habits the numbers of chosen tasks should be a segment of consecutive integers containing no less than 2 numbers, i. e. a sequence of form $l,l+1,...,r$ for some 1<=l&lt;r<=n .

Every task $i$ has an integer number $a_{i}$ associated with it denoting how many man-hours are required to complete the $i$ -th task. Developers are not self-confident at all, and they are actually afraid of difficult tasks. Knowing that, Yura decided to pick up a hardest task (the one that takes the biggest number of man-hours to be completed, among several hardest tasks with same difficulty level he chooses arbitrary one) and complete it on his own. So, if tasks with numbers $[l,r]$ are chosen then the developers are left with $r-l$ tasks to be done by themselves.

Every developer can spend any integer amount of hours over any task, but when they are done with the whole assignment there should be exactly $a_{i}$ man-hours spent over the $i$ -th task.

The last, but not the least problem with developers is that one gets angry if he works more than another developer. A set of tasks $[l,r]$ is considered good if it is possible to find such a distribution of work that allows to complete all the tasks and to have every developer working for the same amount of time (amount of work performed by Yura doesn't matter for other workers as well as for him).

For example, let's suppose that Yura have chosen tasks with following difficulties: $a=[1,2,3,4]$ , and he has three developers in his disposal. He takes the hardest fourth task to finish by himself, and the developers are left with tasks with difficulties $[1,2,3]$ . If the first one spends an hour on the first task and an hour on the third one, the second developer spends two hours on the second task and the third developer spends two hours on the third task, then they are done, since every developer worked exactly for two hours and every task has been worked over for the required amount of time. As another example, if the first task required two hours instead of one to be completed then it would be impossible to assign the tasks in a way described above.

Besides work, Yura is fond of problem solving. He wonders how many pairs $(l,r)$ ( 1<=l&lt;r<=n ) exists such that a segment $[l,r]$ is good? Yura has already solved this problem, but he has no time to write the code. Please, help Yura and implement the solution for this problem.

输入格式

The first line of input contains two positive integers: $n$ and $k$ $(1<=n<=300000,1<=k<=1000000)$ , the number of tasks in the list and the number of developers in Yura's disposal.

The second line contains $n$ integers $a_{i}$ ( $1<=a_{i}<=10^{9}$ ).

输出格式

Output a single integer — the number of pairs $(l,r)$ satisfying the conditions from the statement.

样例 #1

样例输入 #1

4 3
1 2 3 4

样例输出 #1

3

样例 #2

样例输入 #2

4 2
4 4 7 4

样例输出 #2

6

提示

In the first sample there are three good segments:

1. $[1;3]$ — the hardest task requires $3$ man-hours, so there are tasks left that require $1$ and $2$ man-hours. A solution is to make first developer work on the first task for an hour, while second and third developers work on the second task. Each developer works exactly one hour.
2. $[1;4]$ — the hardest task requires $4$ man-hours, so there are tasks left that require $1$ , $2$ and $3$ man-hours. If the first developer spends an hour on the first task and an hour on the third one, the second developer spends two hours on the second task and the third developer spends two hours on the third task, then they are done, since every developer worked exactly for two hours.
3. $[3;4]$ — the hardest task requires $4$ man-hours, so there is only one task left that requires $3$ man-hours. A solution is to make each developer work for an hour.