Kho báu tri thức

Trong thế giới ảo của game "Kho Báu Tri Thức", \(N\) nhà thám hiểm đang tranh tài trong một vòng đấu cam go. Mỗi nhà thám hiểm thứ \(i\) hiện có một số điểm kỹ năng là \(A_i\). Để tạo động lực cho các thí sinh, ban tổ chức đã đưa ra một hệ thống thưởng đặc biệt dựa trên thứ hạng:

Thứ hạng của một nhà thám hiểm được xác định bằng \(1\) cộng với số lượng các nhà thám hiểm khác có điểm kỹ năng nhỏ hơn hẳn điểm của họ. Ví dụ, nếu có 3 nhà thám hiểm điểm lần lượt là 10, 20, 20:

• Người có 10 điểm sẽ có hạng là \(1 + 0 = 1\) (không ai nhỏ hơn hẳn).
• Hai người có 20 điểm sẽ có hạng là \(1 + 1 = 2\) (có 1 người có 10 điểm nhỏ hơn hẳn).

Nếu một nhà thám hiểm đạt thứ hạng \(R\), họ sẽ nhận được một phần thưởng giá trị là \(N - R\) "đồng vàng tri thức".

Cuộc thi diễn ra liên tục, và \(Q\) lần thay đổi điểm số bất ngờ đã xảy ra. Mỗi lần thay đổi, một nhà thám hiểm cụ thể sẽ có điểm kỹ năng của mình bị biến động. Bạn là người quản lý hệ thống, được giao nhiệm vụ tính toán tổng số đồng vàng tri thức mà tất cả các nhà thám hiểm nhận được sau mỗi lần thay đổi.

Input

Dữ liệu được cung cấp theo định dạng sau:

• Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)), lần lượt là số lượng nhà thám hiểm và số lượng lần thay đổi điểm.
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(-10^9 \le A_i \le 10^9\)), là điểm kỹ năng ban đầu của các nhà thám hiểm.
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(P_j\) và \(V_j\) (\(1 \le P_j \le N\), \(10^9 \le V_j \le 10^9\)). \(P_j\) là chỉ số của nhà thám hiểm bị thay đổi điểm (thí sinh thứ \(P_j\) theo chỉ số 1), và \(V_j\) là lượng điểm được cộng thêm vào điểm hiện tại của họ.

Output

In ra \(Q\) dòng, mỗi dòng là tổng số đồng vàng tri thức mà tất cả các nhà thám hiểm nhận được sau mỗi lần thay đổi.

Example

5 2
1 2 3 4 5
1 -2
5 -2

10
11

Scoring

• \(30\%\) số test có \(N, Q \le 100\).
• \(30\%\) số test có \(N, Q \le 1000\).
• \(40\%\) số test còn lại có \(N, Q \le 10^5\).