Cho một dãy ~a~ gồm ~n~ số nguyên ~a_1, a_2, a_3, \dots, a_n~.

Có ~q~ truy vấn. Mỗi truy vấn chứa hai số nguyên: ~p~ ~(1 \leq p \leq n)~ và ~x~ ~(1\leq x \leq 10^9)~, cho biết giá trị phần tử ~a_p~ được gán thành ~x~. Ví dụ, nếu dãy ~a=[6,5,5,3,6]~, ~p=5~ và ~x = 7~, sau truy vấn này, dãy ~a~ sẽ thành ~[6,5,5,3,7]~.

Một cặp nghịch thế là một cặp chỉ số ~(i, j)~ thỏa mãn ~i<j~ và ~a_i>a_j~. Ví dụ, dãy ~[6,5,5,3,7]~ có ~5~ cặp nghịch thế: ~(1, 2), (1, 3), (1, 4), (2, 3)~ và ~(2, 4)~.

Yêu cầu: Sau mỗi truy vấn, bạn hãy in ra số lượng cặp nghịch thế có trong dãy.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ ~(2 \leq n \leq 10^5~ và ~1 \leq q \leq 10^5)~

• Dòng thứ hai chứa ~n~ số nguyên ~1 \leq a_1, a_2, \dots, a_n \leq 10^9~, các phần tử của dãy số ban đầu.

• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~p~ và ~x~ ~(1 \leq p \leq n~ và ~1 \leq x \leq 10^9)~, mô tả các truy vấn.

Output

In ra ~q~ số nguyên trên ~q~ dòng, số lượng cặp nghịch thế của dãy sau mỗi truy vấn.

Scoring

• Subtask 1 (15 điểm): ~1≤n,q≤5000~;

• Subtask 2 (20 điểm): ~1≤n≤10^5, 1≤q≤10~;

• Subtask 3 (30 điểm): ~1≤n,q≤40000~;

• Subtask 4 (10 điểm): ~1≤a_i≤10^5~;

• Subtask 5 (25 điểm): Không có ràng buộc gì thêm.

Sample Input 1

5 4
6 5 5 3 6
5 7
1 10
2 3
3 8

Sample Output 1

5
6
5
6

Notes

• Sau truy vấn đầu tiên, dãy số trở thành ~[6,5,5,3,7]~ và có ~5~ cặp nghịch thế

• Sau truy vấn thứ hai, dãy số trở thành ~[10,5,5,3,7]~ và có ~6~ cặp nghịch thế

• Sau truy vấn thứ ba, dãy số trở thành ~[10,3,5,3,7]~ và có ~5~ cặp nghịch thế

• Sau truy vấn thứ tư, dãy số trở thành ~[10,3,8,3,7]~ và có ~6~ cặp nghịch thế