有 $n$ 张牌，编号为 $1$ 到 $n$。切牌操作过程如下：

1. 将牌按编号从小到大排列。
2. 选择一个正整数 $k$ ($1 \le k \le n$)，将牌分成 $k$ 堆。每一堆至少包含一张牌，且每一堆中的牌编号必须连续，并按从上到下的顺序从小到大排列。
3. 将这些堆以任意顺序重新排列并排成一行。
4. 从左到右遍历这些堆，对于每一堆，如果堆中还有牌，取出最上面的一张牌并将其放在已排列序列的末尾。
5. 当所有牌都放入排列序列后，停止操作。

例如，对于五张牌 $\{1, 2, 3, 4, 5\}$，它们可以被分成 $\{1\}, \{2, 3\}, \{4, 5\}$，$\{1\}, \{2\}, \{3\}, \{4\}, \{5\}$ 或 $\{1, 2, 3, 4, 5\}$，但不能分成 $\{1\}, \{2, 5\}, \{3, 4\}$，因为这违反了编号连续原则；也不能分成 $\{1\}, \{3, 2\}, \{4, 5\}$，因为这违反了按升序排列的原则。

再举一个例子，对于已经从左到右排列好的三堆牌 $\{1\}, \{4, 5\}, \{2, 3\}$，唯一可能的排列序列是 $\{1, 4, 2, 5, 3\}$。无法得到 $\{1, 2, 4, 5, 3\}$，因为这违反了从左到右的遍历顺序；也无法得到 $\{1, 5, 2, 4, 3\}$，因为这违反了从顶部取牌的原则。

现在给定一个目标牌序，你需要计算有多少种不同的切牌操作可以得到该目标序列。当且仅当牌的分堆方式不同或堆的排列顺序不同时，两种切牌操作被视为不同。

目标序列可能会被修改，每次修改会交换目标序列中两个位置的元素，你需要输出修改后的答案。修改是持久的，即之前的修改会保留。

输入格式

第一行包含两个整数 $n, Q$ ($2 \le n \le 10^5, 1 \le Q \le 10^5$)。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)，表示初始的目标序列。 接下来的 $Q$ 行，每行包含两个整数 $x, y$ ($1 \le x, y \le n, x \neq y$)，表示每次修改中要交换的位置。

输出格式

输出 $Q + 1$ 行。第一行输出修改前的答案，第 $2$ 到 $Q+1$ 行输出每次修改后的答案。

样例

样例输入 1

4 3
1 3 2 4
2 3
1 4
4 2

样例输出 1

3
4
1
2

说明

在样例中，有 4 张牌，初始目标序列为 $\{1, 3, 2, 4\}$。有三种切牌操作可以得到该目标序列：

• $\{1, 2\}, \{3, 4\}$
• $\{1\}, \{3, 4\}, \{2\}$
• $\{1\}, \{3\}, \{2\}, \{4\}$

第一次交换后，目标序列变为 $\{1, 2, 3, 4\}$。有四种切牌操作可以得到该目标序列：

• $\{1, 2, 3, 4\}$
• $\{1\}, \{2, 3, 4\}$
• $\{1\}, \{2\}, \{3, 4\}$
• $\{1\}, \{2\}, \{3\}, \{4\}$