upper_bound Ruby編（paizaランク B 相当）

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

問題

n 人の生徒が受けた、10^9 点満点のテストの採点結果 A_1, A_2, ..., A_n があります。あなたは合格点を自由に設定することができます。合格点が k 点のとき、k 点より大きい点数を取った生徒が合格で、k 点以下の点数を取った生徒が不合格です。

q 個の整数 k_1, k_2, ..., k_q が与えられます。各 k_i について、合格点が k_i のときに合格する生徒の数を答えてください。

入力される値

n
A_1 A_2 ... A_n
q
k_1
k_2
...
k_q

1行目に、生徒の人数 n が与えられます。

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

3行目に、合格点の候補数 q が与えられます。

続く q 行のうち i (1 ≦ i ≦ q) 行目に、合格点の候補 k_i が与えられます。

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

期待する出力

q 行出力してください。i 行目 (1 ≦ i ≦ q) には、合格点を k_i としたときに合格する生徒の数を出力してください。

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

条件

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

・入力はすべて整数

・ 1 ≦ n ≦ 100,000

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

・ 1 ≦ q ≦ 100,000

・ 0 ≦ k_i ≦ 10^9 (1 ≦ i ≦ q)