P12755 [POI 2017 R3] 评分 Grades

翻译来自于 [LibreOJ](https://loj.ac/p/5063)。

**题目译自 [XXIV Olimpiada Informatyczna — III etap](https://sio2.mimuw.edu.pl/c/oi24-3/dashboard/) [Oceny](https://szkopul.edu.pl/problemset/problem/0KG8REkSLNnY5sVkm7Aei_R7/statement/)** 体育老师班上有 $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$ 节课评分时，老师最多能使用的不同分数种类。

**样例 1 解释** 首节课学生顺序为 $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$。 详细子任务附加限制及分值如下表所示。 | 子任务 | 附加限制 | 分值 | | :---: | :--: | :---: | | $1$ | $n, z \leq 2000$ | $24$ | | $2$ | $n \leq 2000, z \leq 300000$ | $8$ | | $3$ | $n, z \leq 100000$ | $30$ | | $4$ | $n \leq 1000000, z \leq 300000$，最多 $15$ 种分数 | $10$ | | $5$ | $n \leq 1000000, z \leq 300000$，仅与相邻学生交换 | $20$ | | $6$ | $n \leq 1000000, z \leq 300000$ | $8$