CF1830E.Bully Sort

On a permutation $p$ of length $n$, we define a bully swap as follows:

• Let $i$ be the index of the largest element $p_i$ such that $p_i \neq i$.
• Let $j$ be the index of the smallest element $p_j$ such that $i \lt j$.
• Swap $p_i$ and $p_j$.

We define $f(p)$ as the number of bully swaps we need to perform until $p$ becomes sorted. Note that if $p$ is the identity permutation, $f(p)=0$.

You are given $n$ and a permutation $p$ of length $n$. You need to process the following $q$ updates.

In each update, you are given two integers $x$ and $y$. You will swap $p_x$ and $p_y$ and then find the value of $f(p)$.

Note that the updates are persistent. Changes made to the permutation $p$ will apply when processing future updates.

对于一个长度为 $n$ 的排列 $p$，我们定义一次“霸凌交换”（bully swap）如下：

• 设 $i$ 是满足 $p_i \neq i$ 的最大元素 $p_i$ 的下标；
• 设 $j$ 是满足 $i \lt j$ 的最小元素 $p_j$ 的下标；
• 交换 $p_i$ 和 $p_j$。

我们定义 $f(p)$ 为将 $p$ 变为升序排列（即恒等排列）所需执行的霸凌交换次数。注意：若 $p$ 本身就是恒等排列，则 $f(p)=0$。

给定 $n$ 和一个长度为 $n$ 的排列 $p$，你需要处理接下来的 $q$ 次更新。

每次更新中，你将收到两个整数 $x$ 和 $y$；你需要先交换 $p_x$ 和 $p_y$，然后计算当前 $p$ 对应的 $f(p)$ 的值。

注意：这些更新是持久化的，即对排列 $p$ 所做的修改将在后续更新中持续生效。

The first line of the input contains two integers $n$ and $q$ ($2 \le n \le 5 \cdot 10^5$, $1 \le q \le 5 \cdot 10^4$) — the length of the permutation and the number of updates.

The second line of input contains $n$ integer $p_1,p_2,\ldots,p_n$ ($1 \leq p_i \leq n$) — the permutation $p$. All elements of $p$ are distinct.

The $i$-th of the next $q$ lines of input contains two integers $x_i$ and $y_i$ ($1 \le x_i \lt y_i \le n$) — describing the $i$-th update.

输入的第一行包含两个整数 $n$ 和 $q$（$2 \le n \le 5 \cdot 10^5$，$1 \le q \le 5 \cdot 10^4$）—— 分别表示排列的长度和更新操作的次数。

输入的第二行包含 $n$ 个整数 $p_1,p_2,\ldots,p_n$（$1 \leq p_i \leq n$）—— 表示排列 $p$。$p$ 中所有元素互不相同。

接下来 $q$ 行中的第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i \lt y_i \le n$）—— 描述第 $i$ 次更新操作。

After each update, output $f(p)$.

每次更新后，输出 $f(p)$。

After the first update, we have $f(p)=5$. The $5$ bully swaps are illustrated below.

• $[\mathbf{1}, 2, \mathbf{8}, 5, 3, 4, 7, 6]$,
• $[1, 2, \mathbf{3}, 5, \mathbf{8}, 4, 7, 6]$,
• $[1, 2, 3, 5, \mathbf{4}, \mathbf{8}, 7, 6]$,
• $[1, 2, 3, 5, 4, \mathbf{6}, 7, \mathbf{8}]$,
• $[1, 2, 3, \mathbf{4}, \mathbf{5}, 6, 7, 8]$.

第一次更新后，我们有 $f(p)=5$。这 $5$ 次“霸凌交换”如下所示：

• $[\mathbf{1}, 2, \mathbf{8}, 5, 3, 4, 7, 6]$,
• $[1, 2, \mathbf{3}, 5, \mathbf{8}, 4, 7, 6]$,
• $[1, 2, 3, 5, \mathbf{4}, \mathbf{8}, 7, 6]$,
• $[1, 2, 3, 5, 4, \mathbf{6}, 7, \mathbf{8}]$,
• $[1, 2, 3, \mathbf{4}, \mathbf{5}, 6, 7, 8]$。