3400 - 优美的序列

总司令给你一个长为 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。

用户上传