在长度为 $$$n$$$ 的排列 $$$p$$$ 上,我们定义欺凌交换如下:
- 令 $$$i$$$ 为最大元素 $$$p_i$$$ 的索引,使得 $$$p_i \neq i$$$。
- 令 $$$j$$$ 为满足 $$$i < j$$$ 的最小元素 $$$p_j$$$ 的索引。
- 交换 $$$p_i$$$ 和 $$$p_j$$$。
我们将 $$$f(p)$$$ 定义为在 $$$p$$$ 排序之前需要执行的欺凌交换次数。请注意,如果 $$$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,\ldots,p_n$$$ ($$$1 \leq p_i \leq n$$$) — 排列 $$$p$$$。 $$$p$$$ 的所有元素都是不同的。
接下来的 $$$q$$$ 输入行的第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i < y_i \le n$$$) — 描述第 $$$i$$$ 更新。
输出
每次更新后,输出$$$f(p)$$$。
示例
输入 #1
8 5 6 2 1 5 3 4 7 8 1 8 2 3 4 7 7 8 3 6
输出 #1
5 6 9 8 7
注意
第一次更新后,我们有 $$$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]$$$。