004 - Number-Collection

問題

YDKは $N$ 個の整数 $a_i$ をコレクションとして所持しています。

彼のコレクションは必ず $a_i$ ≤ $a_j$ ($i$ < $j$) となっています。

$Q$ 個の整数 $v_i$ が与えられるので、YDKが $v_i$ をいくつ所持しているか答えてください。

入出力

入力

1行目に、YDKが所持している整数の個数 $N$ が入力される。

2行目に、YDKが所持している $N$ 個の整数 $a_i$ が空白区切りで入力される。

続いて、$Q$ が一行に入力される。

以下、$Q$ 行にわたって $v_j$ が空白区切りで入力される。

N
a1 a2 ... aN
Q
v1 v2 ... vQ

出力

各 $v_i$ について、YDKが $v_i$ を所持している個数を改行区切りで出力せよ。

制約

• 1 ≤ $N$ ≤ 3,000,000
• -1,000,000,000 ≤ $a_i$,$v_i$ ≤ 1,000,000,000
• 1 ≤ $Q$ ≤ 500,000
• $a_i$ ≤ $a_j$ ($i$ < $j$)

部分点

以下の各条件を満たすテストケースに正解すると、部分点がもらえる。

部分点a [配点の10%]

$N$, $Q$ ≤ 1000 を満たす。

部分点b [配点の10%]

0 ≤ $a_i$ ≤ 1,000,000 を満たす。

部分点c [配点の30%]

$a_i$ ≠ $a_j$ ($i$ ≠ $j$) を満たす。これは、$a_i$は重複しないという意味である。

部分点d [配点の100%]

追加の制約なし。

入出力例

入力例1

3
1 7 12
4
1 12 -1 6

出力例1

1
1
0
0

この例では、YDKは{ $1$, $7$, $12$ }の3数を所持している。

所持を判定する整数は4つあり、$1$は1個、$12$は1個、$-1$は0個、$6$は0個所持しているのでこのように出力する。

なお、これは部分点a,b,c,dのテストケースの一つである。

---

入力例2

7
-4 5 5 5 8 9 9
4
9 5 -1 10000000

出力例2

2
3
0
0

これは、部分点a,dのテストケースの一つである。

hoge

cin, cout は

cin.tie(0), ios::sync_with_stdio(false);

がないとTLEします。

あと、 std::endl を使うと TLE するかもしれません(もしそうなったら cout << '\n' にしてください)。