Yuto et Platina vont jouer à un jeu de sous-tableau non décroissant. Le jeu se joue sur un tableau $A$ de longueur $N$.

Yuto choisit d'abord un entier, puis Platina choisit un entier. Les nombres sélectionnés par les joueurs doivent être dans l'intervalle de $L$ à $R$, inclus. Soient $a$ et $b$ les deux entiers sélectionnés, ordonnés de telle sorte que $a \le b$. Le score obtenu dans le jeu est alors le nombre de paires $(i, j)$ telles que $a \le i \le j \le b$ et que l'intervalle $[i, j]$ forme un sous-tableau non décroissant dans le tableau $A$.

Nous disons que $[i, j]$ forme un sous-tableau non décroissant lorsque, pour tout $x$ et $y$ tels que $i \le x \le y \le j$, il est vrai que $A[x] \le A[y]$.

Yuto souhaite minimiser le score, et Platina souhaite le maximiser. Ce jeu est si amusant que nous allons y jouer $T$ fois. Toutes les parties utiliseront le même tableau $A$, mais des parties différentes peuvent utiliser des valeurs de $L$ et $R$ différentes.

En supposant que les deux joueurs jouent de manière optimale, trouvez le nombre de points qu'ils obtiendront dans chacune des parties jouées.

Entrée

La première ligne contient deux entiers $N$ et $T$ ($1 \le N, T \le 500\,000$) : la longueur du tableau et le nombre de parties jouées, respectivement.

La deuxième ligne contient les valeurs du tableau $A[1], A[2], A[3], \dots, A[N]$ ($1 \le A[i] \le 10^9$).

Chacune des $T$ lignes suivantes décrit une partie par deux entiers positifs $L_i$ et $R_i$ ($1 \le L_i \le R_i \le N$) : les valeurs de $L$ et $R$ à utiliser pour cette partie.

Sortie

Pour chaque partie, affichez le score obtenu dans cette partie sur une ligne séparée.

Exemples

Entrée 1

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

Sortie 1

4
1
4
7
3