Đếm nghịch thế

Cho dãy số nguyên \(a\) gồm \(n\) số nguyên. Số nghịch thế của \(a\) là số cặp \(i, j\) sao cho \(1 ≤ i < j ≤ n\) và \(a_{i} > a_{j}\) . Ta thực hiện \(Q\) biến đổi trên \(a\), mỗi biến đổi có dạng:

Tăng \(a_{i}\) lên một lượng bằng x.

Yêu cầu in ra sau số nghịch thế của \(a\) sau mỗi truy vấn

Input

• Dòng đầu chứa \(n, Q\)

• Dòng tiếp theo chứa \(n\) số tự nhiên: \(a_{1}, a_{2}, . . . , a_{n}\)

• \(Q\) dòng tiếp theo mỗi dòng chứa \(i, s\). Công thức tính \(x\) là: \(x = |s + sum|\%(2 × 10^9 + 1) − 10^9\). Ở đây sum là tổng các kết quả của các truy vấn trước truy vấn này

Output

Gồm \(Q\) dòng ghi kết quả tương ứng

Example

4
1 2 3 4
2
3 999999998
3 1000000003

1
1

Scoring

\(1 ≤ n, Q ≤ 10^5, 0 ≤ s ≤ 2 × 10^9\), \(−10^9 ≤ a_{i} ≤ 10^9\) trong mọi thời điểm

• \(30\%\) test: \(n, Q ≤ 10^4\)