P8895 "DPOI-1" Beautiful Sequence

#### Update on 2022.12.18: Added one set of hack testdata targeting @[zhuoxingmu](https://www.luogu.com.cn/user/421155), placed at #21, worth $5$ points. #### Update on 2022.12.18: Added one set of hack testdata targeting @[大眼仔Happy](https://www.luogu.com.cn/user/537046), placed at #22, worth $5$ points. #### Update on 2025.7.7: Added two sets of hack testdata from ticket , placed at #23 and #24. #21 to #24 are all changed to $0$ points. ------------ No, Commander-in-Chief.

The Commander-in-Chief gives you a sequence $a$ of length $n$. He thinks that this $a$ may not be beautiful enough, and he wants to reorder it into a sequence $a'$ to make it beautiful. We call a sequence $a$ of length $n$ beautiful if and only if $\exists i \in [1,n]$ such that: - $\forall j \in [1, i)$, $a_j > a_{j + 1}$. - $\forall j \in (i, n]$, $a_j > a_{j - 1}$. He orders you to find how many different $a'$ can be obtained by reordering $a$. Since the result may be very large, you only need to output it modulo $p$. A fixed $a$ is too boring, so he gives you $m$ modifications. Each modification is of the form `x k`, meaning set $a_x \leftarrow k$. You need to output the current answer after each modification.

The first line contains three integers $n, m, p$. The second line contains $n$ integers $a_1, a_2, \cdots, a_n$. The next $m$ lines each contain two integers $x, k$, representing one modification operation.

Output a total of $m + 1$ lines. Each line contains one integer, representing the required value for the initial state and after each modification.

#### Explanation for Sample #1 For the initial state, the valid $a'$ are $[2, 1, 2, 3], [3, 2, 1, 2]$, for a total of $2$. For $a = [1, 2, 4, 3]$ after the first modification, the valid $a'$ are $[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]$, for a total of $8$. #### Explanation for Sample #2 This sample satisfies the constraints of test points $15 \sim 20$. #### Constraints | Test Point ID | $n \leq$ | $m \leq$ | Special Condition | | :------: | :------: | :------: | :------: | | $1 \sim 2$ | $10$ | $10$ | None | | $3 \sim 4$ | $100$ | $100$ | None | | $5 \sim 6$ | $10^3$ | $10^3$ | None | | $7 \sim 10$ | $10^5$ | $10^5$ | None | | $11 \sim 12$ | $5 \times 10^5$ | $0$ | $a$ is a **permutation** | | $13 \sim 14$ | $5 \times 10^5$ | $0$ | None | | $15 \sim 20$ | $5 \times 10^5$ | $5\times 10^5$ | None | For $100\%$ of the data, $1 \leq n \leq 5 \times 10^5$, $0 \leq m \leq 5 \times 10^5$, $2 \leq p \leq 10^9$, and $1 \leq a_i, k, x \leq n$. Translated by ChatGPT 5