Background

Update on 2022.12.18: Added one set of hack testdata targeting

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

Update on 2022.12.18: Added one set of hack testdata targeting @大眼仔Happy, placed at #22, worth $5$ points.

Update on 2025.7.7: Added two sets of hack testdata from ticket https://www.luogu.com.cn/ticket/XQCA458514, placed at #23 and #24. #21 to #24 are all changed to $0$ points.

No, Commander-in-Chief.

Problem Description

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.

Input Format

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 Format

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

4 1 998244353
1 2 2 3
3 4

2
8

见下发文件 sequence2.in

见下发文件 sequence2.out

Hint

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

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