SWAPS - Counting inversions

no tags 

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.

Input

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 containing 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

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

Example

Input:
10
2 6 6 4 7 6 3 5 9 1 
7
8 8
5 1
5 6
10 5
7 1
10 10
4 6

Output:
17
18
16
13
14
8
6

hide comments
agrawal117: 2019-07-13 21:21:54

@Aman Shrivastava->> integers between 1 and 50000

mamnoonsiam: 2017-06-21 16:37:29

Solved in one go ... works O(n^2) code :')

seyedssz: 2017-05-01 09:32:30

Using segment wiht each node a BIT ->
N(log(N)^2) + Q(log(N)^2) -> TLE
N(log(N)) + Q(log(N)^2) -> AC
So Nice and like it

Last edit: 2017-05-03 15:14:26
Dipjal: 2017-03-16 01:07:24

At single go! :D

bicsi: 2015-05-02 16:55:32

Solved using sqrt(n) - length sequence preprocessing and fast read ^_^! Even though my complexity was (I think) worse than it should have been ( O( sqrt(n) * log(50000) ) per query ), it seemed to go rather well in practice (0.96 on time). Is there a solution in O(log(n)) per query?

Last edit: 2015-05-02 16:56:10
Naman Taneja: 2015-01-12 21:05:14

Nice Question ! A little optimization is required

Last edit: 2015-01-14 21:26:59
Archit Jain: 2014-09-14 14:42:42

segment tree giving tle?
Help

Aman Shrivastava: 2014-09-13 06:19:18

limits of Ai???

Last edit: 2014-09-13 06:19:31

Added by:Gogu
Date:2006-05-31
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource: