Yuto 和 Platina 即將進行一場「非遞減子陣列遊戲」。此遊戲在一個長度為 $N$ 的陣列 $A$ 上進行。

Yuto 首先說出一個整數，隨後 Platina 也說出一個整數。玩家所選的數字必須在 $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