AT_abc473_e.K-Divisible Subarrays

You are given a sequence of length $N$ consisting of non-negative integers: $A=(A _ 1,A _ 2,\ldots,A _ N)$ .

Define the score of a sequence of length $1$ or more consisting of sequences of non-negative integers, $S=(S _ 1,S _ 2,\ldots,S _ k)$, as the number of sequences $S _ i\ (1\le i\le k)$ whose sum of elements is divisible by $K$.

Find the maximum possible score of a sequence of non-negative integer sequences obtained by dividing $A$ into one or more contiguous subsequences. Here, dividing a sequence $A$ of length $N$ into one or more contiguous subsequences means choosing a sequence of integers $l=(l _ 1,l _ 2,\ldots,l _ k)\ (1=l _ 1\lt l _ 2\lt\cdots\lt l _ k\le N)$ of length $1$ or more, and forming the following $k$ sequences.

• $(A _ {l _ i},A _ {l _ i+1},\ldots,A _ {l _ {i+1}-1})\ (1\le i\le k)$ (Here, let $l _ {k+1}=N+1$.)

给你一个长度为 $N$ 的非负整数序列：$A=(A _ 1,A _ 2,\ldots,A _ N)$。

定义一个由一个或多个非负整数序列组成的序列 $S=(S _ 1,S _ 2,\ldots,S _ k)$（其中每个 $S_i$ 长度至少为 $1$）的得分为：满足其元素之和能被 $K$ 整除的子序列 $S_i\ (1\le i\le k)$ 的个数。

求将 $A$ 划分为一个或多个连续子序列后，所能得到的所有非负整数序列序列的最大可能得分。这里，将长度为 $N$ 的序列 $A$ 划分为一个或多个连续子序列，是指选择一个长度至少为 $1$ 的整数序列 $l=(l _ 1,l _ 2,\ldots,l _ k)\ (1=l _ 1\lt l _ 2\lt\cdots\lt l _ k\le N)$，并构造如下 $k$ 个序列：

• $(A _ {l _ i},A _ {l _ i+1},\ldots,A _ {l _ {i+1}-1})\ (1\le i\le k)$（此处令 $l _ {k+1}=N+1$。）

The input is given from Standard Input in the following format:

$N$ $K$
$A _ 1$ $A _ 2$ $\ldots$ $A _ N$

输入从标准输入中按以下格式给出：

$N$ $K$
$A _ 1$ $A _ 2$ $\ldots$ $A _ N$

Output the answer.

输出答案。

Sample 1 Explanation:
For example, $A$ can be divided into four contiguous subsequences as $(6),(8,2),(2),(6,4)$. The sums of the elements of the second and fourth sequences are multiples of $10$, so the score of $((6),(8,2),(2),(6,4))$ is $2$.

$A$ cannot be divided so that the score is $3$ or more, so output 2.

Constraints

• $1\le N\le2\times10 ^ 5$
• $1\le K\le10 ^ 9$
• $0\le A _ i\lt K$
• All input values are integers.

样例 1 解释：
例如，$A$ 可被划分为四个连续子序列：$(6),(8,2),(2),(6,4)$。其中第二和第四个子序列的元素之和均为 $10$ 的倍数，因此划分 $((6),(8,2),(2),(6,4))$ 的得分为 $2$。

无法将 $A$ 划分为得分 $\geq 3$ 的形式，故输出 2。

限制条件

• $1\le N\le2\times10 ^ 5$
• $1\le K\le10 ^ 9$
• $0\le A _ i\lt K$
• 所有输入值均为整数。