题目背景

Update on 2022.12.18：新增一组针对

https://www.luogu.com.cn/user/421155

Update on 2022.12.18：新增一组针对 @大眼仔Happy 的 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$		无
$3 \sim 4$	$100$
$5 \sim 6$	$10^3$
$7 \sim 10$	$10^5$
$11 \sim 12$	$5 \times 10^5$	$0$	$a$ 为一个排列
$13 \sim 14$			无
$15 \sim 20$		$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$。