小朋友分数计算问题

一、问题描述

有 n 个小朋友按顺序排成一列，每个小朋友手中持有一个可正可负的整数数字。

对于每个小朋友，其特征值的定义为：排在他前面（包含他自己）的小朋友中，连续若干个（至少一个）小朋友手中数字之和的最大值。

老师需要给每个小朋友确定一个分数，具体规则如下：

1. 第一个小朋友的分数等于他的特征值。
2. 对于其他小朋友（从第二个小朋友开始），其分数是排在他前面的所有小朋友中（不包含他自己），小朋友分数与该小朋友特征值之和的最大值。

请计算出所有小朋友分数中的最大值，并保持该最大值的符号，将其绝对值对 p 取模后输出。

二、输入格式

第一行输入两个正整数 n 和 p，以空格分隔。其中 n 表示小朋友的数量，p 用于后续取模运算。 第二行输入 n 个整数，相邻两个整数之间用空格分隔，依次表示每个小朋友手中的数字。

三、输出格式

输出仅一行，包含一个整数，表示所有小朋友分数的最大值对 p 取模（保持符号）后的结果。

四、数据范围

1. 对于 50% 的数据：
   • 1 ≤ n ≤ 1,000。
   • 1 ≤ p ≤ 1,000。
   • 所有数字的绝对值均不超过 1000。
2. 对于 100% 的数据：
   • 1 ≤ n ≤ 1,000,000。
   • 1 ≤ p ≤ 10^9。
   • 所有数字的绝对值均不超过 10^9。

五、样例

1. 样例输入 1

5 997
1 2 3 4 5

样例输出 1

21

样例解释 1： 小朋友的特征值依次为 1、3、6、10、15，分数依次为 1、2、5、11、21，最大值 21 对 997 取模后为 21。

2. 样例输入 2

5 7
-1 -1 -1 -1 -1

样例输出 2

-1

样例解释 2： 小朋友的特征值依次为 -1、-1、-1、-1、-1，分数依次为 -1、-2、-2、-2、-2，最大值 -1 对 7 取模后为 -1。