T103785 墙(wall)

$Trump$先生喜欢墙。他特别喜欢那种看上去参差不齐实际上十分有序的墙。 具体来说，如果把墙的高度表示成长度为$L$的一个数列，这个序列满足以下要求： 1. 存在一条以第一个数为起点的上升子序列，它的长度大于 $\displaystyle \frac{L}{2}$ 2. 存在一条以第一个数为起点的下降子序列，它的长度大于 $\displaystyle \frac{L}{2}$ 3. 不存长度超过 2 的连续单调子序列 $Trump$先生的手下克劳恩皮斯已经修好了一堵墙，它的高度可以表示为一个 长度为 $n$ 的排列。为了迎合 $Trump $先生的喜好以及节省经费，她想要保留原排 列的一个子序列，使得 $Trump$ 先生能够喜欢高度为这个子序列的墙。 那么，请你告诉她，这样的子序列有多少个？答案对一个模数 $p$ 取模。

第一行为两个整数 $n,p$ 接下来为一行$n$个整数，代表已经修好的墙的高度

输出一行一个整数，代表答案

**【样例解释 】** 子序列分别是$\{2\},\{1\},\{3\},\{2,1,3\}$ 对于 $8\%$的数据,满足 $n \le 8$ 对于 $20\%$的数据,满足 $n \le 50$ 对于 $32\%$的数据,满足 $n \le 200$ 对于 $48\%$的数据,满足 $n \le 700$ 对于 $64\%$的数据,满足 $n \le 2000$ 对于另外 $8\%$ 的数据,满足已经修好的墙的高度是$\{1,2,3,\dots,n\}$ 对于另外 $8\%$ 的数据,满足 $p=2$ 对于 $100\%$的数据,满足 $1 \le n \le 6000,2 \le p \le 1000000000$ 注意本题空间限制与另外两题不同。