这是一个交互式问题。

有 $n$ 把钥匙和 $n$ 把锁，编号均为 $1$ 到 $n$。每把钥匙 $i$ 恰好能打开一把锁 $i$。

考虑以下开锁算法：

1. 固定一个排列 $p_1, p_2, \dots, p_n$ 表示钥匙的使用顺序。
2. 令 $x$ 为当前钥匙的索引，$y$ 为当前锁的编号。初始时，$x = 1$，$y = 1$。
3. 尝试用钥匙 $p_x$ 打开锁 $y$。
4. 如果尝试成功，将 $y$ 加 $1$；如果 $y$ 等于 $n$，则算法结束。
5. 如果 $x$ 不等于 $n$，则将 $x$ 加 $1$，否则将其设为 $1$。
6. 回到第 3 步。

第 3 步耗时一秒，其余步骤瞬间完成。

请确定对于 $k+1$ 个排列，打开所有锁所需的总时间：这 $k+1$ 个排列包括给定的排列 $p$，以及通过翻转 $p$ 的给定连续区间所构造的 $k$ 个排列。

交互

评测程序将依次输出查询。一旦参赛程序输出了给定查询的答案，评测程序将继续输出下一个查询。

输入格式

第一行包含两个整数 $n$ 和 $k$ ($2 \le n \le 100\,000$; $1 \le k \le 100\,000$)。 第二行包含 $n$ 个不同的整数 $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$)。 接下来的 $k$ 行，每行包含两个整数 $a$ 和 $b$ ($1 \le a < b \le n$)。这意味着查询的排列为 $p_1, p_2, \dots, p_{a-1}, p_b, p_{b-1}, \dots, p_{a+1}, p_a, p_{b+1}, \dots, p_{n-1}, p_n$。

输出格式

对于给定的 $k+1$ 个排列中的每一个，输出一行，包含一个整数：打开所有锁所需的秒数。

样例

样例输入 1

4 2
1 2 3 4
2 3
1 4

样例输出 1

4
8
13

样例输入 2

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

样例输出 2

3
6
6
5
6