問題文

門松列 とは $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\le i\le N)$ が空白区切りで与えられます.

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

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

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

• $1\le N\le 2\times {10}^5$
• $1\le a_i\le {10}^9$
• $1\le Q\le 2\times {10}^5$
• $1\le L_i\le H_i\le {10}^9$

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

出力

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

$i(1\le i\le 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