Problem : 87 - 佇列

Problem Statistics

Solved Member: 11　　Submission: 37　　User Tried: 12

Statement:

想像一個情況，你好不容易來到了Comiket，但是這裡卻不是如你想像的一般好。

簡單來講，你被擠在了一群肥宅的中間，一共有 N 個人就這樣排成了一條直線。剛好前面有蘿莉的Cosplay，所以大家會不自覺的往前看。但是，由於非常的擁擠，所以視線也非常的差，更別說是被前面比自己高的人擋住這種事情了！每個隊伍都會有它的不滿指數，每個人的不滿程度是「在他前面但是身高卻比自己高的人數」，而整條隊伍的不滿程度就是每個人不滿程度的總和。

正好，這時候Staff要過來整隊了，Staff整隊一共會做 M 次交換的動作，每次交換兩個人的位置。Staff不希望它自己交換的隊伍不滿程度太高，以免發生暴動。它想知道在每一次交換之後的不滿程度有多大。

Input:Output:

第 1 行有 1 個正整數 N ，代表有多少人在排隊。
第 2 行有 N 個數字，分別代表從前面到後面每個人的身高。
第 3 行有 1 隔正整數 M ，代表交換動作的次數。
第 4 行之後有 M 行，每行有 2 個數字 A,B ，代表Staff要交換從前面數過來第 A 以及第 B 個人的位置。

n ≤ 20000
m ≤ 2000
1 ≤ 每個人的身高 ≤ 10^9

第 1 行起輸出最剛開始隊伍的不滿程度。
接下來有 M 行，請分別輸出每次交換完之後的不滿程度。

Sample Input:Sample Output:

3
130 150 140
2
2 3
1 3

1
0
3

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	500ms	65536kb
1	500ms	65536kb	5
2	500ms	65536kb	5
3	500ms	65536kb	5
4	500ms	65536kb	5
5	500ms	65536kb	5
6	500ms	65536kb	5
7	500ms	65536kb	5
8	500ms	65536kb	5
9	500ms	65536kb	5
10	500ms	65536kb	5
11	500ms	65536kb	5
12	500ms	65536kb	5
13	500ms	65536kb	5
14	500ms	65536kb	5
15	500ms	65536kb	5
16	500ms	65536kb	5
17	500ms	65536kb	5
18	500ms	65536kb	5
19	500ms	65536kb	5
20	500ms	65536kb	5