「DPOI-1」优美的序列

#### Update on 2022.12.18：新增一组针对 @[zhuoxingmu](https://www.luogu.com.cn/user/421155) 的 Hack 数据，放置于 #21，分值为 $5$ 分。 #### Update on 2022.12.18：新增一组针对 @[大眼仔Happy](https://www.luogu.com.cn/user/537046) 的 Hack 数据，放置于 #22，分值为 $5$ 分。 ------------ 不可以，总司令。

总司令给你一个长为 $n$ 的序列 $a$。 他认为这个 $a$ 现在也许不够优美，他希望将其重排为一个 $a'$，使之变得优美。 我们称一个长为 $n$ 的序列 $a$ 优美，当且仅当 $\exists i \in [1,n]$，满足： - $\forall j \in [1, i)$，$a_j > a_{j + 1}$。 - $\forall j \in (i, n]$，$a_j > a_{j - 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$ 行，每行一个整数，表示初始状态下及每次修改后所求的值。

4 1 998244353
1 2 2 3
3 4

2
8

见下发文件 sequence2.in

见下发文件 sequence2.out

#### 样例 #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$ 的限制。 #### 数据范围 | 测试点编号 | $n \leq$ | $m \leq$ | 特殊条件 | | :------: | :------: | :------: | :------: | | $1 \sim 2$ | $10$ | $10$ | 无 | | $3 \sim 4$ | $100$ | $100$ | 无 | | $5 \sim 6$ | $10^3$ | $10^3$ | 无 | | $7 \sim 10$ | $10^5$ | $10^5$ | 无 | | $11 \sim 12$ | $5 \times 10^5$ | $0$ | $a$ 为一个**排列** | | $13 \sim 14$ | $5 \times 10^5$ | $0$ | 无 | | $15 \sim 20$ | $5 \times 10^5$ | $5\times 10^5$ | 无 | 对于 $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$。