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

Input

• 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_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.

Output

• 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

Sample

Input #1

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

Output #1

5
3
4

Hint

• 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 ~.

Problem source: Free Contest thi thử HSG QG V2