Une séquence $A_1, A_2, \ldots, A_N$ de longueur $N$ est donnée. Écrivez un programme qui traite les requêtes suivantes :

• m k : Parmi les sous-séquences de $A_1, A_2, \ldots, A_m$, la longueur maximale d'une sous-séquence dont la longueur de la plus longue sous-séquence croissante ne dépasse pas $k$. ($1 \le k \le m \le N$)

Entrée

La première ligne contient la longueur de la séquence $N$ et le nombre de requêtes $Q$. ($1 \le N \le 50{,}000$, $1 \le Q \le 200{,}000$)

La deuxième ligne contient $A_1, A_2, \ldots, A_N$. ($1 \le A_i \le 50{,}000$)

Les $Q$ lignes suivantes contiennent chacune une requête au format décrit ci-dessus.

Sortie

Pour chaque requête, affichez la réponse sur une ligne séparée.

Exemples

Exemple d'entrée 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

Exemple de sortie 1

4
6
5
8
7
11