Hay ~n~ edificios en una fila numerados ~1, 2,\dots, n~, de izquierda a derecha. Estás a la izquierda del primer edificio. Puedes ver un edificio si es más alto que todos los edificios a su izquierda.

Tu tarea es procesar ~q~ consultas: Si solo existieran edificios en el rango ~[a, b]~, ¿cuántos edificios verías?

Entrada

• La primera línea tiene dos enteros ~n~ y ~q~: el número de edificios y consultas.
• La segunda línea tiene n enteros ~h_1, h_2,\dots, h_n~: las alturas de los edificios.
• Finalmente, hay ~q~ líneas que describen las consultas. Cada línea tiene dos enteros ~a~ y ~b~.

Salida

Para cada consulta, imprime un entero: el número de edificios visibles.

Restricciones

• ~1 \leq n \leq 10^5~
• ~1 \leq q \leq 2 \cdot 10^5~
• ~1 \leq h_i \leq 10^9~
• ~1 \leq a \leq b \leq n~

Ejemplo de Entrada

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

Ejemplo de Salida

1
3
1