总司令给你一个长为 $n$ 的序列 $a$。

他认为这个 $a$ 现在也许不够优美，他希望将其重排为一个 $a'$，使之变得优美。

我们称一个长为 $n$ 的序列 $a$ 优美，当且仅当 $\exists i \in [1,n]$，满足

• $\forall j \in [1, i)$，$a_j > aj+1$。
• $\forall j \in (i, n]$，$a_j > aj-1$。

他命令你求出 $a$ 经过重排可以得到多少个不同的 $a'$。由于结果可能很大，你只需要求出结果对 $p$ 取模的值。

由于一个固定的 $a$ 太无趣了，于是他给你 $m$ 次修改，每次修改形如 x k，表示令 $a_x \leftarrow k$。你需要在每次修改后求出当前的答案。

第一行，三个整数 $n, m, p$；

第二行，$n$ 个整数 $a_1, a_2, \cdots, a_n$；

接下来 $m$ 行，每行两个整数 $x, k$，表示一次修改操作。

共 $m + 1$ 行，每行一个整数，表示初始状态下及每次修改后所求的值。

样例 #1 解释

对于初始状态，满足条件的 $a'$ 有 $[2, 1, 2, 3], [3, 2, 1, 2]$，共 $2$ 个。

对于第一次修改后的 $a = [1, 2, 4, 3]$，满足条件的 $a'$ 有 $[1, 2, 3, 4], [2, 1, 3, 4], [3, 1, 2, 4], [4, 1, 2, 3], [3, 2, 1, 4], [4, 2, 1, 3], [4, 3, 1, 2], [4, 3, 2, 1]$，共 $8$ 个。

样例 #2 解释

该样例满足测试点 $15 \sim 20$ 的限制。

数据范围

对于 $100\%$ 的数据，$1 \leq n \leq 5 \times 10^5$，$0 \leq m \leq 5 \times 10^5$，$2 \leq p \leq 10^9$，$1 \leq a_i, k, x \leq n$。

用户上传