SP861 SWAPS - Counting inversions

You are given a sequence A of **N** (**N**≤250000) integers between 1 and 50000. On this sequence you have to apply **M** (**M**≤10000) operations of the form: modify the i-th element in the sequence and then say how many inversions are there in the sequence. The number of inversions in a sequence is given by the number of pairs (i,j) with i < j and Ai > Aj.

The first line of input contains the number **N** and the next line contains the numbers that form the sequence. After that follows the number **M** and then **M** lines, each containig 2 integers X and Y, meaning that new value of the X-th element of the sequence is Y and that you should count the number of inversions in the modified sequence.

Output must contain **M** lines, the i-th line of output containg the number of inversions in the sequence after the first i operations.