Dany jest ciąg $A_1, A_2, \ldots, A_N$ o długości $N$. Każdy element ciągu jest liczbą całkowitą od $1$ do $N$, wszystkie są parami różne. Napisz program wykonujący następujące zapytania:

• l r: wypisz długość najdłuższego rosnącego podciągu (LIS) ciągu $(A_l, A_{l+1}, \ldots, A_r)$.

Wejście

Pierwszy wiersz zawiera długość $N$ ciągu oraz liczbę $Q$ zapytań.

Następne $Q$ wierszy zawiera po jednym zapytaniu w formacie opisanym powyżej.

Wyjście

Dla każdego zapytania wypisz odpowiedź w osobnym wierszu.

Przykład

Wejście 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

Wyjście 1

4
4
3
2
1
2
2
3
4
4