对于一个元素互不相同的序列 $a_1, a_2, \cdots, a_n$，我们定义一次合法的操作如下:

• 选取一个 $i \in [2, n-1]$,满足 $a_{i-1} < a_i < a_{i+1}$。
• 将 $a_{i+1}$ 移动到 $a_{i-1}$ 之前。也就是说假设原序列中 $i-1,i,i+1$ 位置的值分别为 $a_{i-1}, a_i, a_{i+1}$，则新的序列中 $i-1,i,i+1$ 位置的值分别为 $a_{i+1},a_{i-1},a_i$。

比如，$a=[1, 2, 3, 4, 5]$，如果在这一次操作中选取 $i=3$,序列将会变为 $[1,4,2,3,5]$。

我们定义一个序列是合法的，当且仅当它能够由一个单调上升的序列通过有限多次操作得到。

给定一个长度为 $n$ 的排列 $a_1, a_2, \cdots, a_n$，有 $q$ 次修改,每次修改形如交换 $a_x$ 和 $a_y$ 的值。你需要在每次修改后，回答最小的正整数 $k$，满足 $a_k, a_{k+1}, \cdots, a_n$ 为一个合法的序列。不难发现，任意长度为 $1$ 的序列均为合法序列，因而最小的正整数 $k$ 一定存在，且唯一。

输入格式

第一行两个整数 $n, q$。

第二行一行 $n$ 个整数，用空格隔开，依次表示 $a_1, a_2, \cdots, a_n$。

接下来 $q$ 行，每行两个整数 $x, y$，描述一次修改。

输出格式

输出 $q$ 行，每行一个整数，表示答案。

样例数据

样例输入

7 5
6 7 2 1 5 3 4
3 1
3 1
7 5
1 6
6 5

样例输出

3
4
6
7
4

样例解释

在第三次操作后，序列变为 6 7 2 1 4 3 5。

对于长度为 $1$ 的子序列，显然其合法，因而 $a_7$ 是一个合法的序列。

对于长度为 $2$ 的子序列 3 5，由于其初始时候有序，显然其合法。因而 $a_6\,a_7$ 是一个合法的序列。

对于长度为 $3$ 的子序列 4 3 5，由于从初始状态只能转移到 3 4 5 和 5 3 4，显然其非法，因而 $a_5\,a_6\,a_7$ 是一个非法的序列。

类似的，我们总可以说明当 $k=1,2,3,4$ 时，$a_k,a_{k+1},\cdots, a_n$ 非法。

因此答案为 $6$。

子任务

• Subtask 1($10\%$): 保证 $n \leq 10$
• Subtask 2($20\%$): 保证 $n \leq 100$
• Subtask 3($30\%$): 保证 $n \leq 5\,000$
• Subtask 4($40\%$): 无特殊限制。

对于所有测试数据，保证 $2 \leq n \leq 100\,000$，$1 \leq q \leq 100\,000$。

对于每一次询问，满足 $1 \leq x,y \leq n$，$x \ne y$。

保证 $a_i$ 是一个 $[1,n]$ 的排列。