题目描述

给定一个长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$，其中 $0 \le a_i < p$。

请选择一个连续区间 $a_l, a_{l+1}, \dots, a_r$（$1 \le l \le r \le n$），使得该子段和对 $p$ 取模的结果尽可能大。

形式化地，你需要最大化：

其中 $\bmod$ 表示取模运算。输出这个最大值。

输入格式

第一行包含两个整数 $n$ 和 $p$，分别表示序列长度和模数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示给定的序列。

输出格式

输出一行一个整数，表示最大可能的子段和对 $p$ 取模的结果。

样例输入 1

3 10
3 5 7

样例输出 1

8

样例输入 2

4 7
2 3 1 4

样例输出 2

6

说明

样例解释

对于样例 $2$，选择整个序列 $[2, 3, 1, 4]$，和为 $10$，$10 \bmod 7 = 3$。选择子段 $[2, 3]$，和为 $5$。选择子段 $[3, 4]$，和为 $7$，$7 \bmod 7 = 0$。选择子段 $[1, 4]$，和为 $5$。选择子段 $[2, 3, 1]$，和为 $6$，$6 \bmod 7 = 6$。因此最大值为 $6$。

其它样例说明

• 样例 3：见选手目录下的 sum/sum3.in 与 sum/sum3.ans，该测试用例满足测试点 $1 \sim 8$ 的约束条件。
• 样例 4：见选手目录下的 sum/sum4.in 与 sum/sum4.ans，该测试用例满足测试点 $9 \sim 12$ 的约束条件。
• 样例 5：见选手目录下的 sum/sum5.in 与 sum/sum5.ans，该测试用例满足测试点 $13 \sim 16$ 的约束条件。
• 样例 6：见选手目录下的 sum/sum6.in 与 sum/sum6.ans，该测试用例满足测试点 $17 \sim 20$ 的约束条件。

数据范围

对于 $100\%$ 的数据，满足以下约束条件：

• $1 \le n \le 2 \times 10^5$
• $1 \le p \le 10^9$
• $0 \le a_i < p$

各测试点的附加限制如下表所示：

点击下载大样例