CF549F.Yura and Developers

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

尤拉有一支由 $k$ 名开发人员组成的团队，以及一个编号为 $1$ 到 $n$ 的任务列表。尤拉计划在本周选择一些任务来完成。由于 Looksery 公司奇特的习惯，所选任务的编号必须构成一个长度至少为 $2$ 的连续整数区间，即形如 $l,\ l+1,\ \dots,\ r$ 的序列，其中 $1 \leq l < r \leq n$。

每个任务 $i$ 都关联一个整数 $a_i$，表示完成第 $i$ 个任务所需的“人时”（man-hours）数量。开发人员非常缺乏自信，实际上害怕困难的任务。考虑到这一点，尤拉决定亲自完成所有被选任务中最难的一个（即所需人时最多的那个；若存在多个难度相同且均为最大值的任务，则任选其一）。因此，若选择的任务区间为 $[l,\ r]$，则开发人员需自行完成剩余的 $r - l$ 个任务。

每位开发人员可在任意任务上投入任意整数小时数，但当整个任务集完成后，第 $i$ 个任务上投入的总人时数必须恰好为 $a_i$。

此外，开发人员还有一个问题：若某位开发人员的工作量超过另一位，则他会生气。称一个任务区间 $[l,\ r]$ 是“好的”，当且仅当存在一种工作分配方式，使得所有任务均能完成，且每位开发人员的工作时间完全相等（尤拉本人的工作量对其他开发人员及他自己均无影响）。

例如，假设尤拉选择的任务难度为 $a = [1,\ 2,\ 3,\ 4]$，且他手下有 $3$ 名开发人员。他将最难的第 $4$ 项任务（需 $4$ 人时）留给自己完成，开发人员则需处理其余难度为 $[1,\ 2,\ 3]$ 的任务。若第一位开发人员在第一个任务上工作 $1$ 小时、在第三个任务上工作 $1$ 小时；第二位开发人员在第二个任务上工作 $2$ 小时；第三位开发人员在第三个任务上工作 $2$ 小时，则全部任务均被完成，且每位开发人员均工作了恰好 $2$ 小时，每个任务也均获得了所需的人时数。再举一例，若第一个任务所需人时数改为 $2$（而非 $1$），则无法按上述方式分配任务。

除了日常工作外，尤拉还热衷于解题。他想知道：有多少对 $(l,\ r)$（满足 $1 \leq l < r \leq n$）使得区间 $[l,\ r]$ 是“好的”？尤拉已手动解出该问题，但没有时间编写代码。请帮助尤拉实现该问题的解决方案。

The first line of input contains two positive integers: n and k (1 ≤ n ≤ 300 000, 1 ≤ k ≤ 1 000 000), 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 ≤ 109).

输入的第一行包含两个正整数：$n$ 和 $k$（$1 ≤ n ≤ 300\,000$，$1 ≤ k ≤ 1\,000\,000$），分别表示任务列表中的任务数量以及尤拉可调用的开发人员数量。

第二行包含 $n$ 个整数 $a_i$（$1 ≤ a_i ≤ 10^9$）。

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

输出一个整数——满足题目中所述条件的数对 $(l,\ r)$ 的个数。

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.

在第一个样例中，存在三个“好”区间：

1. [1;3] — 最难的任务需要 3 个人工小时，因此剩余任务所需人工小时数分别为 1 和 2。一种可行方案是：第一位开发者花费 1 小时处理第一个任务，第二位和第三位开发者共同花费 1 小时处理第二个任务。每位开发者恰好工作 1 小时。
2. [1;4] — 最难的任务需要 4 个人工小时，因此剩余任务所需人工小时数分别为 1、2 和 3。若第一位开发者分别在第一个任务和第三个任务上各花费 1 小时，第二位开发者在第二个任务上花费 2 小时，第三位开发者在第三个任务上花费 2 小时，则所有任务均可完成，且每位开发者恰好工作 2 小时。
3. [3;4] — 最难的任务需要 4 个人工小时，因此仅剩一个任务，需 3 个人工小时。一种可行方案是：三位开发者每人工作 1 小时。