Collecting Numbers II

题目描述

给定一个数组，数组中恰好包含每个数字 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 \le n, m \le 2 \cdot 10^5$ $1 \le a,b \le n$

标签: CSES2217|排序和搜索

来源

CSES2217|排序和搜索