E. 霸凌排序
每次测试的时间限制：10 秒
每次测试的内存限制：1024 兆字节

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

• 设 $i$ 是满足 $p_i \neq i$ 的最大元素 $p_i$ 的索引。
• 设 $j$ 是满足 $i < j$ 的最小元素 $p_j$ 的索引。
• 交换 $p_i$ 和 $p_j$。

定义 $f(p)$ 为使 $p$ 变为有序（即 $p_i = i$）所需的霸凌交换次数。注意，如果 $p$ 已经是恒等排列，则 $f(p) = 0$。

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

在每个更新中，你会得到两个整数 $x$ 和 $y$。你需要交换 $p_x$ 和 $p_y$，然后求出 $f(p)$ 的值。

注意，更新是持久化的：对排列 $p$ 的更改会影响后续更新。

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

第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$（$1 \le p_i \le n$）—— 排列 $p$。所有 $p_i$ 互不相同。

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

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

示例

输入

8 5
6 2 1 5 3 4 7 8
1 8
2 3
4 7
7 8
3 6

输出

5
6
9
8
7

注释
第一次更新后，$f(p) = 5$。这 $5$ 次霸凌交换如下：

$[1,2,8,5,3,4,7,6]$，
$[1,2,3,5,8,4,7,6]$，
$[1,2,3,5,4,8,7,6]$，
$[1,2,3,5,4,6,7,8]$，
$[1,2,3,4,5,6,7,8]$。