Roy and Query (Hard Version)
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
Input  Output 



First test case:
First Query : L= 1, X= 3, R=5.
Information
 ID
 1082
 Difficulty
 4
 Category
 (None)
 Tags
 (None)
 # Submissions
 44
 Accepted
 18
 Accepted Ratio
 41%
 Uploaded By
Related
In following contests: