题目描述

给定一个长度为 $n$ 的数组 $a$ 和 $m$，求一个区间 $[l,r]$，使得 $(\sum_{i=l}^{r}a_i) \bmod M$ 的值最大。

输入格式

第一行两个整数 $n$，$m$。

第二行 $n$ 个整数 $a_i$。

输出格式

输出一行一个整数，表示答案。

5 13
10 9 5 -5 7

11

提示

$n \le 2 \times 10^5,~m,a_i \le 10^{18}$

题目来源

By Sbullet