给定一个由 $n$ 个正整数组成的序列 $a$ (下标从1开始) 和一个质数模数 $p$ 。

你可以将序列里任意数量的数取相反数。试最大化一个式子的值：

• 定义一个 $[l,r]$ $(1\le l \le r \le n)$区间的价值: 如果把 $a$ 序列里下标从 $l$ 到 $r$ （包含边界）的值都乘起来, 对 $p$ 取模, 如果结果是 $1$,区间价值为$0$, 否则区间价值为 $1$ 。
• 定义一个式子的值为序列的共 $n\times (n+1)/2$ 个不同的区间的价值的和

并输出一个式子的值的最大值。

（负数 $x$ 对 $p$ 取模的结果为 $(-(-x \mod p)+p)\mod p$ 。

第一行两个整数 $n,p$ 。

接下来 $n$ 个正整数 $a_i$，含义如题意描述所示。

$n\leq 3\times 10^{5},$ $2\leq p\leq 10^9+7,$ $a_i\leq p$

输出一行一个整数，表示上式的最大值