You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

翻译自 CSES-2217 题。

题目描述

给你一个数组，其中 $1\dots n$ 之间的每个数字都正好包含一次。您的任务是按递增顺序收集从 $1$ 到 $n$ 的数字。

每一轮，你都要从左到右遍历数组，收集尽可能多的数字。

给定 $m$ 个操作，交换数组中的两个数字，你的任务是输出每次操作后的轮数。

输入格式

第一行有两个整数 $n$ 和 $m$，分别代表数组大小和操作次数。

下一行有 $n$ 个整数 $x_1,x_2,\dots,x_n$，分别代表数组中的数字。

最后，有 $m$ 行描述操作。每行有两个整数 $a$ 和 $b$，分别代表下标位置 $a$ 和 $b$ 的数字被交换。

输出格式

输出 $m$ 个整数，分别表示每次交换后的轮数。

样例

5 3
4 2 1 5 3
2 3
1 5
2 3

2
3
4

说明/提示

$1 \leq n,m \leq 2\cdot 10^5$；

$1 \le a,b \le n$ 。