题目描述

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

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

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

输入格式

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

第二行有 $n$ 个整数 $x_1, x_2, \ldots, 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 \le n, m \le 2 \times 10^5$
• $1 \le a, b \le n$