問題文

門松列 とは $3$ 個の要素からなる数列 $A_1, A_2, A_3$ で以下の 2 つの条件を満たすものです。

• $A_1, A_2, A_3$ は全て異なる
• $3$ つの要素の中で $A_2$ が最も大きい、または、$A_2$ が最も小さい

与えられた数列の要素数3の部分列（連続でなくてもよい）のうち, 門松列であるものを部分門松列と呼ぶことにします.

このとき, 各クエリに対して, 真ん中の要素 (上の例における $A_2$) の値が $L$ 以上 $H$ 以下となる部分門松列の個数を求めてください.

ただし, 部分列の各要素は並び替えてはいけません.

また, 取り出した部分列の各要素が同じでも, 取り出した位置が異なれば別々に数えることとします.

入力

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

1行目に, 数列の要素数 $N$ が与えられます.

続いて2行目に, 数列の各要素の値 $a_i \ (1 \leq i \leq N)$ が空白区切りで与えられます.

続いて3行目に, クエリの数 $Q$ が与えられます.

続いて4行目から $Q$ 行の間, 真ん中の要素の値の範囲を決める値 $L_i$, $H_i$ が空白区切りで与えられます.

入力は, 以下の制約を満たします.

• $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$

なお, 部分点などはありませんが, 1_small*.inは $N = Q = 200, \ a_i \leq 10000$ となっています.

出力

出力は $Q$ 行からなります.

$i \ (1 \leq i \leq Q)$ 行目には, 真ん中の要素の値が $L_i$ 以上 $H_i$ 以下となる部分門松列の個数を出力してください.

最後に改行してください.

サンプル

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