Soit une séquence $A_1, A_2, \ldots, A_N$ de longueur $N$. Chaque élément de la séquence est un entier distinct compris entre $1$ et $N$. Écrire un programme pour exécuter les requêtes suivantes :

• l r : afficher la longueur de la plus longue sous-séquence strictement croissante (LIS) de $(A_l, A_{l+1}, \ldots, A_r)$.

Entrée

La première ligne contient la longueur $N$ de la séquence et le nombre $Q$ de requêtes.

Les $Q$ lignes suivantes contiennent chacune une requête telle que décrite ci-dessus.

Sortie

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

Exemples

Entrée 1

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

Sortie 1

4
4
3
2
1
2
2
3
4
4