#include<bits/stdc++.h> #define ll long long const ll MaxN = 1e6; const ll Base = (ll)1e9; struct pii { ll high, low; friend inline pii operator +(const pii &a, const pii &b) { pii c; c.high = a.high + b.high; c.low = a.low + b.low; if (c.high >= 0 && c.low >= Base) { c.high += c.low / Base; c.low = c.low % Base; } if (c.high <= 0 && c.low <= -Base) { c.high += c.low / Base; c.low = c.low % Base; } if (c.high > 0 && c.low < 0) { c.high--; c.low += Base; } if (c.high < 0 && c.low >= Base) { c.high++; c.low -= Base; } return c; } friend inline bool operator <(const pii &a, const pii &b) { if (a.high == b.high) return a.low < b.low; else return a.high < b.high; } friend inline pii max(const pii &a, const pii &b) { if (a < b) return b; else return a; } }; ll N, P; inline void getInt(ll &ans) { int f = 1; long long x = 0; char ch; do {ch = getchar(); if (ch == '-') f = -1;} while (ch < '0' || ch > '9'); do {x = x*10 + ch - '0'; ch = getchar();} while (ch >= '0' && ch <= '9'); ans = (f == 1) ? x : -x; } pii w[MaxN], q[MaxN], s[MaxN], data[MaxN], ans; int main() { getInt(N); getInt(P); for (int i = 1; i <= N; ++i) { getInt(data[i].low); } ans = s[1] = q[1] = w[1] = data[1]; for (int i = 2; i <= N; ++i) { w[i] = max(w[i - 1] + data[i], data[i]); q[i] = max(q[i - 1], w[i]); s[i] = (i == 2) ? s[1] + s[1] : max(s[i - 1], s[i - 1] + q[i - 1]); ans = max(ans, s[i]); // debug1(); } std::cout << (((ans.high%P)*Base)%P + (ans.low%P))%P << std::endl; return 0; }