题目描述

题目译自 XXIV Olimpiada Informatyczna — III etap Oceny

体育老师班上有 $n$ 名学生。学年即将结束，是时候为每位学生评定期末成绩了。老师根据学生运动能力，为每人分配了一个从 $1$ 到 $n$ 的数值 $a_i$，数值越大表示运动能力越强，每位学生的 $a_i$ 各不相同。课堂开始时，学生按顺序排成一列，老师从左到右依次评分。评分范围从 $1$ 到 $n$，共有 $n$ 种不同分数。

老师希望评分满足以下要求：

• 对于任意两学生 $v$ 和 $u$，若 $v$ 的运动能力强于 $u$，则 $v$ 的分数不得低于 $u$，否则显失公平。
• 对于任意两学生 $v$ 和 $u$，若 $v$ 站在 $u$ 右侧，晚于 $u$ 被评分，则 $v$ 的分数不得低于 $u$，以免其感到失落。
• 在满足上述条件的前提下，老师希望尽可能使用多种不同分数。

每节课学生以某种顺序排队。老师习惯固定顺序，但应学生请求，同意每两节课间有两名学生互换位置。老师尚未决定在哪节课评分。帮助他编写程序，计算每节课若在当时评分，最多能使用多少种不同分数。

输入格式

第一行包含两个正整数 $n, z$，分别表示学生人数和剩余课次。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(1 \leq a_i \leq n)$，表示首节课按排队顺序的学生运动能力值，互不相同。

接下来的 $z-1$ 行描述位置交换，第 $i$ 行包含两个整数 $p_i, q_i$ $(1 \leq p_i < q_i \leq n)$，表示第 $i$ 节课后，站在位置 $p_i$ 和 $q_i$ 的学生将在下节课前互换位置。

输出格式

输出 $z$ 行，第 $i$ 行包含一个整数，表示第 $i$ 节课评分时，老师最多能使用的不同分数种类。

3 4
1 2 3
1 3
1 2
2 3

3
1
1
2

首节课学生顺序为 $1,2,3$，每人可获不同分数。第 $2$ 节课顺序为 $3,2,1$，第3节课为 $2,3,1$，这两节课学生 $1$ 因能力最低且最后评分，分数不得高于或低于他人。第 $4$ 节课顺序为 $2,1,3$，学生 $3$ 可获更高分数，学生 $1$ 和 $2$ 须同分。

附加样例

1. 小型样例，首节课奇数位置学生能力高于偶数位置，最后一节按能力升序排列。
2. $n=2000, z=n/2+1$，奇数 $i$ 的 $a_i=i+1$，偶数 $i$ 的 $a_i=i-1$，$p_i=2i-1, q_i=2i$（连续学生对交换），分数种类从 $n/2$ 增至 $n$。
3. $n=z=300000, a_i=i$（学生按能力升序），$p_i=i, q_i=i+1$（学生 $n$ 依次与所有人交换），分数种类从 $n$ 降至 $1$。

数据范围与提示

详细子任务附加限制及分值如下表所示。