题目描述

给定一个长度为$\red{n}$的序列$\red{a}$以及常数$\red{k，}$序列从$\red{1}$开始编号.记

$\red{f(l,r)=\sum^{r}_{i=l}{a_i}-max^{r}_{i=l}{\{a_i\}}}$

求合法的正整数对$\red{(l,r)}$的数量，满足$\red{1≤}$$\red{l<r≤}$$\red{n，}$且$\red{k|f(l,r)}$。

输入格式

第一行两个正整数 $\red{n }$和 $\red{k }$。

第二行包含 $\red{n }$个正整数，第 $\red{i }$个正整数表示 $\red{ai}$。

输出格式

一行一个正整数，表示答案。

样例

输入样例1

4 3

1 2 3 4

输出样例1

3

输入样例2

4 2

4 4 7 4

输出样例2

6

提示

数据范围

对于 $\red{30\% }$的数据，$\red{n ≤}$ $\red{3000}$；

对于另外 $\red{20\% }$的数据，数列 $\red{a }$为随机生成；

对于 $\red{100\% }$的数据，$\red{1 ≤}$ $\red{n ≤}$ $\red{3 ×}$ $\red{10^5 , 1 ≤}$ $\red{k ≤}$ $\red{10^6 , 1 ≤}$ $\red{ai ≤}$ $\red{10^9}$。