{"raw_statement":[{"iden":"background","content":"#### Update on 2022.12.18：新增一组针对 @[zhuoxingmu](https://www.luogu.com.cn/user/421155) 的 Hack 数据，放置于 #21，分值为 $5$ 分。\n#### Update on 2022.12.18：新增一组针对 @[大眼仔Happy](https://www.luogu.com.cn/user/537046) 的 Hack 数据，放置于 #22，分值为 $5$ 分。\n#### Update on 2025.7.7：新增两组 hack 数据，来自工单 <https://www.luogu.com.cn/ticket/XQCA458514>，放置于 #23、#24。#21~#24 全部改为 $0$ 分。\n------------\n不可以，总司令。"},{"iden":"statement","content":"总司令给你一个长为 $n$ 的序列 $a$。\n\n他认为这个 $a$ 现在也许不够优美，他希望将其重排为一个 $a'$，使之变得优美。\n\n我们称一个长为 $n$ 的序列 $a$ 优美，当且仅当 $\\exists i \\in [1,n]$，满足：\n\n- $\\forall j \\in [1, i)$，$a_j > a_{j + 1}$。\n- $\\forall j \\in (i, n]$，$a_j > a_{j - 1}$。\n\n他命令你求出 $a$ 经过重排可以得到多少个不同的 $a'$。由于结果可能很大，你只需要求出结果对 $p$ 取模的值。\n\n由于一个固定的 $a$ 太无趣了，于是他给你 $m$ 次修改，每次修改形如 `x k`，表示令 $a_x \\leftarrow k$。你需要在每次修改后求出当前的答案。"},{"iden":"input","content":"第一行，三个整数 $n, m, p$；\n\n第二行，$n$ 个整数 $a_1, a_2, \\cdots, a_n$；\n\n接下来 $m$ 行，每行两个整数 $x, k$，表示一次修改操作。"},{"iden":"output","content":"共 $m + 1$ 行，每行一个整数，表示初始状态下及每次修改后所求的值。"},{"iden":"note","content":"#### 样例 #1 解释\n对于初始状态，满足条件的 $a'$ 有 $[2, 1, 2, 3], [3, 2, 1, 2]$，共 $2$ 个。\n\n对于第一次修改后的 $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$ 个。\n#### 样例 #2 解释\n该样例满足测试点 $15 \\sim 20$ 的限制。\n#### 数据范围\n| 测试点编号 | $n \\leq$ | $m \\leq$ | 特殊条件 |\n| :------: | :------: | :------: | :------: |\n| $1 \\sim 2$ | $10$ | $10$ | 无 |\n| $3 \\sim 4$ | $100$ | $100$ | 无 |\n| $5 \\sim 6$ | $10^3$ | $10^3$ | 无 |\n| $7 \\sim 10$ | $10^5$ | $10^5$ | 无 |\n| $11 \\sim 12$ | $5 \\times 10^5$ | $0$ | $a$ 为一个**排列** |\n| $13 \\sim 14$ | $5 \\times 10^5$ | $0$ | 无 |\n| $15 \\sim 20$ | $5 \\times 10^5$ | $5\\times 10^5$ | 无 |\n\n对于 $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$。"}],"translated_statement":null,"sample_group":[["4 1 998244353\n1 2 2 3\n3 4","2\n8"],["见下发文件 sequence2.in","见下发文件 sequence2.out"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}