题目描述

给定一个由非负整数组成的长度为 $N$ 的序列 $A = (A_1, A_2, \ldots, A_N)$。

对一个由非负整数序列组成的、长度不小于 $1$ 的序列 $S = (S_1, S_2, \ldots, S_k)$，定义它的得分为：$S_1, \ldots, S_k$ 当中，元素总和能被 $K$ 整除的那些序列的个数。

请求出：把 $A$ 划分成一段或多段连续子序列所得到的序列组，其得分的最大值。

这里，把长度为 $N$ 的序列 $A$ 划分成一段或多段连续子序列，是指取一个长度不小于 $1$ 的整数序列 $l = (l_1, l_2, \ldots, l_k)$，满足 $1 = l_1 < l_2 < \cdots < l_k \le N$，然后构造出下面 $k$ 个序列（其中约定 $l_{k+1} = N+1$）：

• $(A_{l_i}, A_{l_i+1}, \ldots, A_{l_{i+1}-1}) \quad (1 \le i \le k)$

输入格式

N K
A_1 A_2 ... A_N

输出格式

输出答案。

输入示例 1

6 10
6 8 2 2 6 4

输出示例 1

2

示例 1 说明

例如可以把 $A$ 划分成 $(6), (8,2), (2), (6,4)$ 这 $4$ 段。第 $2$ 段与第 $4$ 段的元素之和分别是 $10$ 和 $10$，都是 $10$ 的倍数，所以 $((6),(8,2),(2),(6,4))$ 的得分是 $2$。

不存在得分不小于 $3$ 的划分方式，故输出 2。

输入示例 2

8 1
0 0 0 0 0 0 0 0

输出示例 2

8

示例 2 说明

$K = 1$ 时任何整数都能被整除，所以把每个元素单独切成一段就能得到 $8$ 分，这也是上限。这组数据用来检验 $K = 1$ 的边界。

输入示例 3

30 8
5 0 4 2 7 3 2 3 2 4 0 1 4 0 4 1 7 5 2 5 0 3 6 6 2 3 2 2 4 2

输出示例 3

8

示例 3 说明

$N = 30$ 而答案只有 $8$，说明大部分位置切开都不划算。这组数据规模适中但结构不平凡，可以用来对拍：把它和「枚举所有 $2^{29}$ 种划分」的暴力程序比对，能有效验证做法是否正确。

约束条件

• $1 \le N \le 2 \times 10^5$
• $1 \le K \le 10^9$
• $0 \le A_i < K$
• 所有输入值均为整数