Cho dãy số gồm N số nguyên dương a1, a2, … aN. Một dãy con ai1, ai2, ai3, …, aik với i1 < i2 < i3 < … < ik được gọi là dãy con tăng khi ai1 < ai2 < ai3 < … < aik. Cho Q truy vấn, truy vấn thứ i (i=1..Q) được mô tả bởi hai số nguyên dương pi và xi. Với mỗi truy vấn, thay phần tử ở vị trí pi bằng xi. Lưu ý: việc thay đổi này chỉ có tác dụng với một truy vấn đó.

Yêu cầu: Tìm độ dài dãy con tăng dài nhất sau mỗi truy vấn.

Dữ liệu: Vào từ tệp văn bản LIS.INP gồm:

• Dòng đầu tiên chứa hai số nguyên dương N, Q (N, Q ≤ 3.10^5).
• Dòng thứ hai gồm N số nguyên dương a1, a2, …, aN (ai ≤ 10^9).
• Q dòng tiếp theo, mỗi dòng gồm hai số nguyên dương pi và xi (pi ≤ N, xi ≤ 10^9) mô tả một truy vấn.

  Kết quả: Ghi ra tệp văn bản LIS.OUT 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 (i=1..Q).

Ví dụ:

    LIS.INP                      LIS.OUT
    7  3                        5
    1  5  3  1  2  4  6         3
    2  2                        4
    7  3
    4  100  5

Ràng buộc:

• Có 3 điểm có: N, Q ≤ 300;
• Có 3 điểm tiếp theo có: N, Q ≤ 3000;
• Có 1 điểm còn lại không có ràng buộc gì thêm.