Yuto 和 Platina 正在玩一个“非递减子数组游戏”。该游戏在一个长度为 $N$ 的数组 $A$ 上进行。

Yuto 首先说出一个整数，随后 Platina 也说出一个整数。玩家选择的数字必须在区间 $[L, R]$（包含 $L$ 和 $R$）内。设两位玩家选择的整数为 $a$ 和 $b$，并按 $a \le b$ 的方式排序。游戏得分定义为满足 $a \le i \le j \le b$ 且区间 $[i, j]$ 在数组 $A$ 中构成非递减子数组的数对 $(i, j)$ 的数量。

我们称 $[i, j]$ 构成非递减子数组，是指对于所有满足 $i \le x \le y \le j$ 的 $x$ 和 $y$，都有 $A[x] \le A[y]$。

Yuto 希望最小化得分，而 Platina 希望最大化得分。这个游戏非常有趣，我们将进行 $T$ 次游戏。所有游戏使用相同的数组 $A$，但不同游戏可能使用不同的 $L$ 和 $R$ 值。

假设两位玩家都采取最优策略，请计算出每场游戏中他们最终得到的得分。

输入格式

第一行包含两个整数 $N$ 和 $T$ ($1 \le N, T \le 500\,000$)，分别表示数组的长度和游戏的次数。

第二行给出数组的值 $A[1], A[2], A[3], \dots, A[N]$ ($1 \le A[i] \le 10^9$)。

接下来的 $T$ 行，每行通过两个正整数 $L_i$ 和 $R_i$ ($1 \le L_i \le R_i \le N$) 描述一场游戏，即该场游戏所使用的 $L$ 和 $R$ 的值。

输出格式

对于每场游戏，在单独的一行中输出该游戏的得分。

样例

样例输入 1

8 5
7 10 3 1 9 5 5 2
1 5
2 2
5 8
1 8
3 5

样例输出 1

4
1
4
7
3