体育老师班上有 $n$ 名学生。学年即将结束，是时候给学生们打最终成绩了。为此，老师给每名学生分配了一个 $1$ 到 $n$ 之间的运动指数 $a_i$，反映他们的运动能力。在每节课开始时，学生们排成一列。老师按从左到右的顺序给出成绩。每个成绩可以是 $1$ 到 $n$ 之间的任意整数。（是的，每名学生都有可能获得唯一的成绩！）

然而，老师希望成绩满足以下条件： 对于任意两名学生 $v$ 和 $u$，如果 $v$ 的运动指数大于 $u$ 的运动指数，那么 $v$ 的成绩不能低于（差于）$u$ 的成绩，因为这显然是不公平的。 对于任意两名学生 $v$ 和 $u$，如果 $v$ 在队列中排在 $u$ 之后（即被评分的时间更晚），那么 $v$ 的成绩必须低于（差于）$u$ 的成绩，因为这会让 $v$ 感到非常难过。 * 老师希望在遵守上述规则的前提下，最大化他们给出的不同成绩的数量。

每次上课时，学生们都会排成一个有序的队列，老师习惯于某种特定的顺序。但在学生的请求下，老师同意在连续的课程之间，两名学生可以交换在队列中的位置。老师还没有决定何时给出最终成绩。请编写一个程序，确定在学期结束前的每一节课中，如果老师决定在那时给所有学生打最终成绩，他最多能给出多少种不同的成绩。

输入格式

输入的第一行包含两个正整数 $n$ 和 $z$，分别表示学生人数和即将进行的课程节数。

第二行包含一个由 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) 组成的序列，指定了老师偏好的顺序下（即剩余课程的第一节课时）学生们的运动指数。这些指数互不相同，因此构成了 $1, 2, \dots, n$ 的一个排列。因此，我们可以通过运动指数来标识一名学生。

接下来的 $z-1$ 行描述了交换操作。具体来说，第 $i$ 行包含两个整数 $p_i$ 和 $q_i$ ($1 \le p_i < q_i \le n$)，表示在第 $i$ 节课期间位于队列中第 $p_i$ 位和第 $q_i$ 位的学生将在下一节课前交换位置。

输出格式

输出共 $z$ 行。第 $i$ 行的数字应对应老师在第 $i$ 节课期间可以给出的不同成绩的最大数量。

样例

样例输入 1

3 4
1 2 3
1 3
1 2
2 3

样例输出 1

3
1
1
2

说明

样例说明：在第一节课中，学生的顺序是 $1, 2, 3$，因此他们每个人都可以获得不同的成绩。在第二节课中，顺序是 $3, 2, 1$，在第三节课中是 $2, 3, 1$。在这两种顺序下，学生 $1$ 的运动指数最小，因此他不能获得比其他人更好的成绩。同时，由于他是最后被评分的，他也不能获得比其他人更差的成绩。最后，在最后一节课中，学生的顺序是 $2, 1, 3$。此时，学生 $3$ 可以获得比学生 $1$ 和 $2$ 更好的成绩，而学生 $1$ 和 $2$ 必须获得相同的成绩。

子任务

测试集由以下子任务组成。每个子任务内可能包含多个测试组。