题目描述

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

对于一个由非负整数序列组成的、长度为 $1$ 或以上的序列 $S=(S _ 1,S _ 2,\ldots,S _ k)$，定义其得分为满足元素之和能被 $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$。）

输入格式

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

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

输出格式

输出答案。

数据范围

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

6 10
6 8 2 2 6 4

2

例如，可以把 $A$ 划分成四个连续子序列 $(6),(8,2),(2),(6,4)$。其中第二个和第四个序列的元素之和是 $10$ 的倍数，因此 $((6),(8,2),(2),(6,4))$ 的得分为 $2$。

无法把 $A$ 划分成得分为 $3$ 或以上的形式，因此输出 2。

8 1
0 0 0 0 0 0 0 0

8

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

8

• 来源：AtCoder ABC 473 E

子任务设置

• 子任务 1（30 分）：$N \le 2000$。
• 子任务 2（30 分）：$K \le 10$。
• 子任务 3（40 分）：无特殊限制。