Cho một dãy số gồm ~N~ phần tử ~a_1,a_2,...,a_N~. Một dãy con ~a_{i_1}, a_{i_2}, a_{i_3},... a_{i_k}~ với ~i_1 < i_2 < i_3... < i_k~ được gọi là dãy con tăng khi ~a_{i_1} < a_{i_2} < a_{i_3} <...< a_{i_k}~.

Cho ~Q~ truy vấn, truy vấn thứ ~i~ được mô tả bởi hai số nguyên dương ~p_i~ và ~x_i~, yêu cầu: Giả sử thay phần tử ở vị trí ~p_i~ bằng ~x_i~ thì độ dài dãy con tăng dài nhất là bao nhiều? Chú ý rằng giá trị của các phần tử sẽ không thật sự thay đổi sau các truy vấn.

Hãy viết chương trình trả lời ~Q~ truy vấn trên.

Dữ liệu

• Dòng đầu tiên chứa số nguyên dương ~N, Q (N,Q ≤ 300000)~ - số phần tử và số truy vấn.
• Dòng thứ hai gồm ~N~ số nguyên dương ~a_1, a_2, a_3, ..., a_N (a_i ≤ 10^9)~.
• ~Q~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~p_i~ và ~x_i~ ~(p_i ≤ N, x_i ≤ 10^9)~ mô tả một truy vấn.

Kết quả

• Gồm ~Q~ dòng, dòng thứ ~i~ in ra một số nguyên dương là câu trả lời cho truy vấn thứ ~i~

Chấm điểm

• 20% số test tương ứng với 20% số điểm có ~N,Q ≤ 3000~.

Ví dụ

Sample Input 1

7 3
1 5 3 1 2 4 6
2 2
7 3
4 100

Sample Output 1

5
3
4

Giải thích

• Dãy số trong truy vấn thứ nhất sẽ là ~1\ 2\ 3\ 1\ 2\ 4\ 6~. Một trong các dãy con tăng có độ dài ~5~ là ~a_1, a_2, a_3, a_6, a_7~.
• Dãy số trong truy vấn thứ hai sẽ là ~1\ 5\ 3\ 1\ 2\ 4\ 3~. Một trong các dãy con tăng có độ dài ~3~ là ~a_1, a_3, a_6~.
• Dãy số trong truy vấn thứ ba sẽ là ~1\ 5\ 3\ 100\ 2\ 4\ 6~. Một trong các dãy con tăng có độ dài ~4~ là ~a_1, a_5, a_6, a_7~.

Nguồn: Free Contest