Queue

First day of school!

$n$ primary school freshmen are queuing up and each of them owns a student number. Teacher Mr. Cycle finds that the queue is unordered. In order to make the queue more orderly, he has to choose some pairs of students and exchange their positions.

However, Mr. Cycle is a lazy dog and impatient with making plans, so he asks for Miss. Ke's help. Specifically, Miss Ke gives Mr. Cycle a plan list of $m$ position pairs, and each pair $(p_1, p_2)$ means that Mr. Cycle can exchange the student at position $p_1$ and the student at position $p_2$ in the current queue (positions of the queue are numbered from $1$). Mr. Cycle trusts Miss Ke a lot, so he exchanges one by one strictly in the order of the plan list, and writes down the queuing chaotic value $V_i$ after $i$-th exchange for every $1 \le i \le m$.

Now Mr. Cycle wants to know the minimal queuing chaotic value $V = \min_{1\le i \le m}\{V_i\}$ in advance, so that he can stop exchanging at a proper time.

If we denote the student number of the student at position $i$ as $s_i$, the queuing chaotic value of a certain student queue equals the number of inversions, that is, the number of pairs $(i, j)$ such that $1 \le i < j \le n$ and $s_i > s_j$.

The first line contains one integer $T$ $(1 \le T < 10)$ indicating the number of test cases. Then $T$ test cases follows.

The first line of each test case contains one integer $n$ $(1 \le n \le 10^{5})$ indicating the number of students.

The second line contains $n$ integers indicating the students number, the $i$-th integer indicates the student number of the student at the $i$-th position in the initial queue ($0 \le s_i \le 10^{5}$).

Then third line contains one integer $m$ $(1 \le m \le 1000)$ indicating the number of position pairs in the plan list.

For the following $m$ lines, each line describes a position pair $(p_{i1}, p_{i2})$ $(1 \le p_{i1} \le p_{i2} \le N,$ $p_{i2}-p_{i1} \le 100)$.

Output $T$ lines.

For each case, output one line containing one integer: the minimal queuing chaotic value $V$.

1
5
5 4 3 2 1
2
1 5
2 4

0

“红旗杯”第十四届吉林省大学生程序设计竞赛