对于一个元素互不相同的序列 $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]$ 的排列。