Một dãy $A_1, A_2, \ldots, A_N$ độ dài $N$ được cho trước. Hãy viết chương trình xử lý các truy vấn sau:

• m k: Trong số các dãy con của $A_1, A_2, \ldots, A_m$, độ dài lớn nhất của một dãy con mà độ dài dãy con tăng dài nhất của nó không vượt quá $k$. ($1 \le k \le m \le N$)

Dữ liệu vào

Dòng đầu tiên chứa độ dài của dãy $N$ và số lượng truy vấn $Q$. ($1 \le N \le 50\,000$, $1 \le Q \le 200\,000$)

Dòng thứ hai chứa $A_1, A_2, \ldots, A_N$. ($1 \le A_i \le 50\,000$)

$Q$ dòng tiếp theo, mỗi dòng chứa một truy vấn theo định dạng đã 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

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

Dữ liệu ra 1

4
6
5
8
7
11