問題一覧 > 通常問題

No.404 部分門松列

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 29
作問者 : りあんりあん / テスター : antaanta
2 ProblemId : 1072 / 出題時の順位表
問題文最終更新日: 2016-07-22 15:59:22

問題文

門松列 とは $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$ 以下となる部分門松列の個数を出力してください.

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

サンプル

サンプル1
入力
4
1 4 2 3
4
3 4
5 8
2 4
1 1
出力
2
0
3
0

要素数3の部分列は {1, 4, 2}, {1, 4, 3}, {1, 2, 3}, {4, 2, 3} の4通りで,

{1, 2, 3} 以外は門松列になっています.

よって, 部分門松列は {1, 4, 2}, {1, 4, 3}, {4, 2, 3} の3通りです.

サンプル2
入力
5
1 1 1 4 2
4
1 3
3 6
4 4
4 8
出力
0
3
3
3

{1, 4, 2} という部分列が3通り作れます.

サンプル3
入力
6
1 1 4 5 1 4
3
1 4
2 3
1 14514
出力
1
0
4

サンプル4
入力
1
1
1
1 1
出力
0

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。