来源：张老师 2026 CSP-J 4＋1 拓展题 20 套；第 05 套，第 3 题。原题标号：C；原本地编号：Z4P1-05-C。

C. 整除 2

给定一个长度为 $n$ 的数列 $a$，你可以操作任意次，每次选择数列中相邻的两个元素 $u,v$，计算 $w=u+v$，并将 $w$ 插入 $u,v$ 之间，再把 $u,v$ 删除。

求出最终数列中最多能有多少项能被 $p$ 整除。

输入格式

第一行两个整数 $n,p$。

第二行共 $n$ 个数，表示数列 $a$。

输出格式

仅一行一个数，表示答案。

样例

输入样例 1

5 3
1 2 3 1 2

输出样例 1

3

样例 1 说明

两次均选定 $u=1,v=2$，操作后，数列 $a=[3,3,3]$。

数据规模与约定

• 数据点 $1$：$p=2$。
• 数据点 $2\sim3$：$n\le 10$。
• 数据点 $4\sim6$：$n\le 2\times10^3$。
• 数据点 $7\sim10$：无特殊限制。

对于 $100\%$ 的数据，有 $1\le n,p,a_i\le 10^6$。