ある範囲に含まれている整数の個数 (paizaランク B 相当)

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

数列 A = (A_1, A_2, ..., A_n) と、整数の組 (l_1, r_1), (l_2, r_2), ..., (l_q, r_q) が与えられます。

各組 (l_i, r_i) について、数列 A に含まれる値のうち l_i 以上 r_i 以下であるものの個数を求めてください。

入力される値

n
A_1 A_2 ... A_n
q
l_1 r_1
l_2 r_2
...
l_q r_q

1行目に、数列の要素数 n が与えられます。

2行目に、A_i が半角スペース区切りで与えられます。

3行目に、与えられる整数の組の個数 q が与えられます。

続く q 行のうち i (1 ≦ i ≦ q) 行目に、整数の組 (l_i, r_i) が与えられます。

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力

q 行出力してください。

i 行目 (1 ≦ i ≦ q) には、数列 A に含まれる値のうち l_i 以上 r_i 以下であるものの個数を出力してください。

また、末尾に改行を入れ、余計な文字、空行を含んではいけません。

条件

すべてのテストケースにおいて、以下の条件をみたします。

・入力はすべて整数

・ 1 ≦ n ≦ 200,000

・ -10^9 ≦ A_i ≦ 10^9 (1 ≦ i ≦ n)

・ 1 ≦ q ≦ 200,000

・ -10^9 ≦ l_i ≦ r_i ≦ 10^9 (1 ≦ i ≦ q)

入力例1: 10
-45 62 -11 81 75 -90 13 2 97 -32
5
-30 65
-90 -90
-15 85
-50 50
-10 -1