Background

Three hundred years ago, a prehistoric scientific civilization crossed the boundary. An artificial intelligence that surpassed humans appeared, namely the Superman Machine.

Born in secrecy, by the time people realized it, the world was already in “his” hands.

Where he was, what he looked like—no one knew until the very end. But it seemed he could appear anywhere and take on any appearance.

He was neither hostile nor oppressive; he simply had the upper hand in terms of power. He also did not interfere very often. I guess humans did not matter to him.

But even so, he would still help people fulfill their wishes. Demon men, demon dragons, all kinds of unbelievable things—these were created only because someone pursued them.

......

However, one day, the Superman Machine disappeared.

Killed by rust-eating bacteria, or just hiding, or setting off toward the other end of the dimension—people said all kinds of things. All that was left were the Superman Machine’s baffling inventions, and a world that humans themselves had messed up.

This sea of trees must also be a product of the Superman Machine. Magic power can suddenly increase and then be consumed, right? Magic is the ability to draw power from another dimension, a technology beyond human understanding.

Problem Description

Given a sequence $a$, we define an ordered pair $(i,j)$ to be an inversion if and only if $i<j$ and $a_i>a_j$. We say two inversions $(i_1,j_1)$ and $(i_2,j_2)$ are essentially different if and only if $a_{i_1}\ne a_{i_2}$ or $a_{j_1}\ne a_{j_2}$.

Now given the sequence $a$, ask for the number of essentially different inversions.

That is not enough.

Now there are $q$ modifications. Each modification is of the form $x~y$, meaning to change $a_x$ to $y$. The modifications are not independent: each modification affects all later modifications.

You need to output, after each modification, the number of essentially different inversions in the sequence.

To reflect different solution approaches, different test points have different time and memory limits.

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, describing one modification.

Output Format

Output one integer per line.

The first line is the number of essentially different inversions in the initial sequence.

The next $q$ lines each contain one integer; line $i+1$ is the answer after the $i$-th modification.

5
3 1 2 1 5 
1
3 3

3
1

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

3
3
3
1

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

23
25
29
30
24
29
29
29
24
20
20

Hint

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

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

The following are the subtasks:

::cute-table{tuack}

Special Property A: The testdata is guaranteed to be completely random.

Please note the memory limits of some test points.

Translated by ChatGPT 5