Given a sequence $a$, we define a pair $(i, j)$ 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 defined as 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.

That is not all.

There are $q$ modifications, where each modification is given as $x~y$, meaning $a_x$ is changed to $y$. Each modification is not independent, meaning each modification affects all subsequent modifications.

You need to output the number of distinct inversions in the sequence after each modification.

To reflect the different approaches to this problem, different test cases have different time and memory limits.

Input

The first line contains an integer $n$, representing the length of the sequence.

The second line contains $n$ integers $a_i$, representing the sequence $a$.

The third line contains an integer $q$, representing the number of queries.

The following $q$ lines each contain two integers representing a modification.

Output

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

The following $q$ lines each contain an integer, where the $(i+1)$-th line represents the number of distinct inversions in the sequence after the $i$-th modification.

Examples

Input 1

5
3 1 2 1 5 
1
3 3

Output 1

3
1

Input 2

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

Output 2

3
3
3
1

Input 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 3

23
25
29
30
24
29
29
29
24
20
20

Subtasks

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$.

The following are the subtasks (empty cells indicate no special restrictions):

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