题目背景

翻译自 CSES-2217 题。

题目描述

给你一个长度为 $n$ 的数组，其中 $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

样例解释

初始数组为 $[4,2,1,5,3]$。

• 第一次操作交换位置 $2,3$，数组变为 $[4,1,2,5,3]$：第一轮收集 $1,2,3$，第二轮收集 $4,5$，共 $2$ 轮；
• 第二次操作交换位置 $1,5$，数组变为 $[3,1,2,5,4]$：共需 $3$ 轮；
• 第三次操作交换位置 $2,3$，数组变为 $[3,2,1,5,4]$：共需 $4$ 轮。

数据范围

• 对于 $20\%$ 的测试点，保证 $1 \le n, m \le 100$；
• 对于 $50\%$ 的测试点，保证 $1 \le n, m \le 3000$；
• 对于 $100\%$ 的测试点，保证 $1 \le n, m \le 2 \times 10^5$，$1 \le a, b \le n$。