D. Updating Inversions
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of $$$n$$$ integers $$$a_1,a_2, \ldots, a_n$$$.

You are also given $$$q$$$ queries. Each query consists of two integers: $$$p$$$ ($$$1 \le p \le n $$$) and $$$x$$$ ($$$1 \le x \le 10^9$$$), meaning that $$$a_p$$$ will be replaced by $$$x$$$. For example, if $$$a=[6,5,5,3,6]$$$, $$$p=5$$$ and $$$x=7$$$, after the query $$$a$$$ will be equal to $$$[6,5,5,3,7]$$$.

After each query, print the number of inversions in array $$$a$$$. An inversion is a pair of indices $$$(i,j)$$$ where $$$i \lt j$$$ and $$$a_i \gt a_j$$$.

Input

The first line of input contains two integers $$$n$$$ and $$$q$$$ ($$$2 \le n \le 10^5$$$ and $$$1 \le q \le 10^5$$$). The second line of input contains $$$n$$$ integers $$$1 \le a_1,a_2,\ldots,a_n \le 10^9$$$, the elements of the initial array. Each of the next $$$q$$$ lines contains two integers $$$p$$$ and $$$x$$$ ($$$1 \le p \le n$$$, $$$1 \le x \le 10^9$$$), the descriptions of the queries.

Output

Print $$$q$$$ integers, the number of inversions after each query.

Scoring
  • Subtask 1 (15 points): $$$1 \le N,Q \le 5000$$$;
  • Subtask 2 (20 points): $$$1 \le N \le 10^5$$$, $$$1 \le Q \le 10$$$;
  • Subtask 3 (30 points): $$$1 \le N,Q \le 40000$$$;
  • Subtask 4 (10 points): $$$1 \le a_i \le 10^5$$$;
  • Subtask 5 (25 points): No further constraints.
Example
Input
5 4
6 5 5 3 6
5 7
1 10
2 3
3 8
Output
5
6
5
6
Note
  • After the first update the array is $$$[6,5,5,3,7]$$$; there are $$$5$$$ inversions
  • After the second update the array is $$$[10,5,5,3,7]$$$; there are $$$6$$$ inversions
  • After the third uddate the array is $$$[10,3,5,3,7]$$$; there are $$$5$$$ inversions
  • After the fourth update the array is $$$[10,3,8,3,7]$$$; there are $$$6$$$ inversions