Problem Statement

A Kadomatsu sequence is a sequence $A_1, A_2, A_3$ of $3$ elements that satisfies both of the following 2 conditions.

• $A_1, A_2, A_3$ are all distinct
• Among the $3$ elements, $A_2$ is the largest, or $A_2$ is the smallest

Among the subsequences of 3 elements of the given sequence (they need not be contiguous), we call those that are Kadomatsu sequences Kadomatsu subsequences.

For each query, find the number of Kadomatsu subsequences whose middle element (the $A_2$ in the description above) has a value between $L$ and $H$, inclusive.

Note that the elements of a subsequence must not be reordered.

Also, even if the elements of the chosen subsequences are the same, they are counted separately if the positions they are chosen from differ.

Input

$N$
$a_1 \ a_2 \ ... \ a_N$
$Q$
$L_1 \ H_1$
:
$L_Q \ H_Q$

The first line contains the number of elements of the sequence, $N$.

The second line contains the values of the elements of the sequence, $a_i \ (1 \leq i \leq N)$, separated by spaces.

The third line contains the number of queries, $Q$.

Each of the $Q$ lines starting from the fourth line contains the values $L_i$, $H_i$, which determine the range of values of the middle element, separated by a space.

The input satisfies the following constraints.

• $1 \ \leq \ N \ \leq \ 2 \times 10^5$
• $1 \ \leq \ a_i \ \leq \ 10^9$
• $1 \ \leq \ Q \ \leq \ 2 \times 10^5$
• $1 \ \leq \ L_i \ \leq \ H_i \ \leq \ 10^9$

There are no subtasks or the like, but in 1_small*.in, $N = Q = 200, \ a_i \leq 10000$.

Output

The output consists of $Q$ lines.

On the $i \ (1 \leq i \leq Q)$-th line, print the number of Kadomatsu subsequences whose middle element has a value between $L_i$ and $H_i$, inclusive.

Print a newline at the end.

Sample

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

2
0
3
0

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

0
3
3
3

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

1
0
4

1
1
1
1 1

0