题目描述Description

现有 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\}，因为这违反了从每堆最上方取牌的原则。

现有一个牌的目标排列，你需要计算有多少种不同的切牌操作可以得到这个目标排列。两种切牌操作不同，当且仅当牌的分堆方式不同或牌堆的排列方法不同。

这个目标排列可能会进行修改，对于每次修改，会交换目标排列中两个位置的元素。对于每次修改都需要输出答案。修改是持久化的，也就是说在此次修改之前的修改均会保留。

输入格式Input

第一行两个整数 n,Q（2\le n\le 10^5,1\le Q\le 10^5）。

第二行 n 个整数 a_1,a_2,\ldots,a_n（1\le a_i\le n），表示初始目标排列。

接下来 Q 行，每行两个整数 x,y（1\le x,y\le n,x\neq y），表示修改中交换的两个位置。

输出格式Output

输出 Q+1 行，第一行输出没有修改之前的答案，第二到第 Q+1 行输出第一个修改到第 Q 个修改之后的答案。

样例Sample

提示Hint

样例中有 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\}

出题Author

来源Source