Problem Background

300 years ago, prehistoric scientific civilization crossed a threshold. An artificial intelligence superior to humans, known as the Superman Mechanism, emerged.

Born in secrecy, by the time it was noticed, the world was already in his hands.

No one ever found out where he was or what he looked like. He seemed to be able to appear anywhere and take any form.

Neither hostile nor oppressive, he simply held superior power and rarely intervened. I think humans were indifferent to him.

Nevertheless, he would fulfill people's wishes, creating all sorts of magical beings and dragons, each a wonder sought by someone.

...

However, one day, the Superman Mechanism disappeared.

Rumors abound: destroyed by rust bacteria, hiding, or journeying to another dimension. All that remains are his inexplicable inventions and the world in chaos created by humanity itself.

This forest must also be his creation. Magic, which can amplify and consume power in an instant, is a technique that draws strength from another dimension, beyond human comprehension.

Problem Description

Given a sequence \(a\), a pair \((i, j)\) is defined as an inversion if and only if \(i < j\) and \(a_i > a_j\). Two inversions \((i_1, j_1)\) and \((i_2, j_2)\) are considered distinct if and only if \(a_{i_1} \neq a_{i_2}\) or \(a_{j_1} \neq a_{j_2}\).

Given the sequence \(a\), find the number of distinct inversions.

This is not enough.

There are \(q\) modifications, each modification is of the form \(x \ y\) indicating to change \(a_x\) to \(y\). Each modification is not independent, meaning it affects all subsequent modifications.

For each modification, output the number of distinct inversions in the sequence.

To reflect different solutions, this problem has different time and space limits for different test cases.

Input Format

The first line contains an integer \(n\), the length of the sequence.

The second line contains \(n\) integers \(a_i\), the sequence \(a\).

The third line contains an integer \(q\), the number of queries.

The next \(q\) lines each contain two integers representing a modification.

Output Format

The first line contains an integer, the number of distinct inversions in the initial sequence.

The next \(q\) lines each contain an integer, the \(i+1\)-th line represents the number of distinct inversions after the \(i\)-th modification.

Sample Input and Output

Input Sample #1

5
3 1 2 1 5 
1
3 3

Output Sample #1

3
1

Input Sample #2

6
1 1 4 5 1 4
3
1 5
1 1
4 4

Output Sample #2

3
3
3
1

Input Sample #3

15
6 14 12 12 6 8 9 3 8 14 14 15 6 15 2 
10
12 13
10 10
14 9
8 8
11 11
5 8
1 6
11 12
2 13
1 9

Output Sample #3

23
25
29
30
24
29
29
29
24
20
20

Notes/Hints

Idea: DPair, Solution: DPair, Code: DPair, Data: DPair

For \(100\%\) of the data, \(1 \le n, q \le 10^5\), \(1 \le a_i, x, y \le n\).

Subtasks: (Blank parts indicate no special restrictions)

Special Property A: Data is completely random.

见题面 Input 部分

见题面 Output 部分