1.1题目描述

小Y手中有三个长度为n的序列。第一个序列被称为初始值，记为A。 第二个序列被称为特征值，记为B。特征值序列可以由初始值序列计算得到，第i个特征值B为前面i初始值中最大的子段和。形式化地讲，

第三个序列被称为合成值，记为C。合成值序列可以由特征值序列计算得到，第1个合成值C为第1个特征值，第i个合成值C为前i-1个位置中，合成值加特征值的最大值。形式化地讲，

现在给出小Y手中的初始值序列A，请计算合成值序列C中的最大值。输出时请保留符号，并将最大值的绝对值对p取模后输出。 温馨提示:合成值序列的数可能会很大，在计算过程中请大家选择合适的存储方式。

1.2输入描述

输入包含两行。 第一行给出正整数n,p，其中n ≤ 1e6,p ≤1e9。 第二行给出n个整数A;(|A;≤109)，表示初始值序列的第i个数。输入规模较大，建议大家使用较快的读入方式。 对于50%的数据．满足n ≤1000,p ≤1000,Ai ≤1000。

1.3 输出描述

输出一行 表示答案

1.4 样例展示

样例输入 1

5 997

1 2 3 4 5

样例输出1

21

样例输入2

5 7

-1 -1 -1 -1 -1

样例输出 2

-1

1.5时空限制

时间:1 s

空间:256 MB