play-with-segment-again

There is an array of N distinct elements.
Array elements are some permutation of first N natural numbers.(hence they are distinct ) 
Now you are given M pairs.
We call these pairs “bad pairs”.
We define segment of array as  A[L,R] (L ≤ R)
(A[L],A[L+1],...A[R-1],A[R])  i.e  a contiguous sequence of array elements.  
A segment is infected segment if any two adjacent elements in that segment are bad pairs.  
(there exist atleast one bad pair in that infected segment).
More simply: if (a[i-1],a[i]) form bad pair then segment containing these two elements will be infected.
(hence infected segment will be of length atleast 2)
You have to find number of infected segments.

Input : 
First line will contain an integer 'T' (number of test cases ).
For each test case there is an integer 'N' (number of elements in array).
On next line there will be N  distinct integers (array elements).  
On next line there will be an integer M (number of bad pairs)
Next M lines contains two integers (u,v)   : u,v form bad pair.

Note : if (u,v) are bad pair then (v,u) are also bad pair.

Output : 
For each test case output the number of infected segment.

Constraint : 
T ≤ 10
N ≤ 200000
1 ≤ a[i] ≤ N
0 ≤ M ≤ 2*100000
1 ≤ u,v ≤ N
u!=v

Problem setter : Mohd Abdullah

SAMPLE INPUT
4
5
1 4 2 3 5
6
2 1
2 5
4 3
2 3
5 3
1 4

10
1 5 2 9 8 7 3 4 6 10
0

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

7
6 4 3 2 1 5 7
4
7 3
2 1
7 5
6 4

SAMPLE OUTPUT
9
0
9
17

Source: hackerearth | Difficulty: EASY


Solutions: