Se da una secuencia $A_1, A_2, \ldots, A_N$ de longitud $N$. Escribe un programa que procese las siguientes consultas:

• m k: Entre las subsecuencias de $A_1, A_2, \ldots, A_m$, la máxima longitud de una subsecuencia cuya Subsecuencia creciente más larga tenga longitud no mayor a $k$. ($1 \le k \le m \le N$)

Entrada

La primera línea contiene la longitud de la secuencia $N$ y el número de consultas $Q$. ($1 \le N \le 50{,}000$, $1 \le Q \le 200{,}000$)

La segunda línea contiene $A_1, A_2, \ldots, A_N$. ($1 \le A_i \le 50{,}000$)

Las siguientes $Q$ líneas contienen cada una una consulta en el formato descrito anteriormente.

Salida

Para cada consulta, imprime la respuesta en una línea separada.

Ejemplos

Entrada de muestra 1

11 6
9 6 3 1 5 12 8 4 2 2 2
5 1
7 2
9 1
9 2
11 1
11 11

Salida de muestra 1

4
6
5
8
7
11