Yuto y Platina van a jugar un juego de subarreglos no decrecientes. El juego se desarrolla en un arreglo $A$ de longitud $N$.

Yuto dice primero un número entero y, después de eso, Platina dice otro número entero. Los números seleccionados por los jugadores deben estar en el intervalo de $L$ a $R$, inclusive. Sean los dos enteros seleccionados $a$ y $b$, ordenados de tal manera que $a \le b$. Entonces, la puntuación obtenida en el juego es el número de pares $(i, j)$ tales que $a \le i \le j \le b$ y el intervalo $[i, j]$ forma un subarreglo no decreciente en el arreglo $A$.

Decimos que $[i, j]$ forma un subarreglo no decreciente cuando, para cada $x$ e $y$ tales que $i \le x \le y \le j$, es cierto que $A[x] \le A[y]$.

Yuto quiere minimizar la puntuación y Platina quiere maximizarla. Este juego es tan divertido que lo jugaremos $T$ veces. Todos los juegos utilizarán el mismo arreglo $A$, pero los diferentes juegos podrían usar distintos valores de $L$ y $R$.

Asumiendo que ambos jugadores juegan de manera óptima, encuentre el número de puntos que obtendrán en cada uno de los juegos realizados.

Entrada

La primera línea contiene dos enteros $N$ y $T$ ($1 \le N, T \le 500\,000$): la longitud del arreglo y el número de juegos realizados, respectivamente.

En la segunda línea, se proporcionan los valores del arreglo $A[1], A[2], A[3], \dots, A[N]$ ($1 \le A[i] \le 10^9$).

Cada una de las siguientes $T$ líneas describe un juego mediante dos enteros positivos $L_i$ y $R_i$ ($1 \le L_i \le R_i \le N$): los valores de $L$ y $R$ a utilizar para este juego.

Salida

Para cada juego, imprima la puntuación obtenida en ese juego en una línea separada.

Ejemplos

Entrada 1

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

Salida 1

4
1
4
7
3