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 Q which represent the number of query.
In each query you are given three positive integer L, X, R ,
you need to find out number of possible pair \((i,j)\) such that:

\(L <= i < X < j <= R\),

• \(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 : Length of the array \(A[]\).
A[] : Exactly N elements.
Q : Number of Query.
L, X, R: In each query, three positive integer.

\(1<=T<=10^3\)
\(1<=N,Q<=2 * 10^5\)
\(1<=A[]<=10^9\)
\(1<=L<=X<=R<=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
7
1 10 4 9 2 9 9 
3
1 3 5
2 4 5
1 1 1

2
1
0

First test case:
First Query : L= 1, X= 3, R=5.