Cho dãy $A_1, A_2, \ldots, A_N$ có độ dài $N$. Mỗi phần tử trong dãy là một số nguyên phân biệt từ $1$ đến $N$. Hãy viết chương trình thực hiện các truy vấn sau:

• l r: in ra độ dài của dãy con tăng dài nhất (LIS) của $(A_l, A_{l+1}, \ldots, A_r)$.

Dữ liệu vào

Dòng đầu tiên chứa độ dài $N$ của dãy và số lượng $Q$ truy vấn.

$Q$ dòng tiếp theo, mỗi dòng chứa một truy vấn như mô tả ở trên.

Dữ liệu ra

Với mỗi truy vấn, in ra câu trả lời trên một dòng riêng biệt.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

4
4
3
2
1
2
2
3
4
4