Time Limit: 2.0 s

Memory Limit: 256.0 MB

Description

You are given an array \(A[]\) and the length of the array is N. You are also given a positive integer Qwhich represent the number of query.
In each query you are given a positive integer X, you need to find out number of possible pair \((i,j)\) such that,

\(1 <= i < X < j <= N\),

• \(A[i] > A[X] > A[j]\) or \(A[i] < A[X] < A[j]\).

Note : The Difference between easy and hard version on query. Easy version has no bound either left or right but Hard version has.

Input

T : Number of test case.
N : Lenght of the array \(A[]\).
A[] : Exactly N elements.
Q : Number of Query.
X : In each query, a positive integer.

\(1<=T<=10^3\)
\(1<=N,Q<=2 * 10^5\)
\(1<=A[]<=10^9\)
\(1<=X<=N\)
It is gurantee that sum of N and Q over all test case doesn't exceed \(2 * 10^5\)

Output

In each query, print the total number of pair satisfied the conditions.

Sample

1
5
1 6 5 7 2
3
1 3 2

0
2
1

First test case :
Second query X = 3,