Counting Digits 1

You are given a sequence of \(N\) positive integers \(a_1, a_2, \ldots, a_N\). Then you receive \(Q\) queries; the \(i\)-th query provides a positive integer \(b_i\), and you must report how many times \(b_i\) appears in the sequence \(a\).

This problem is meant as practice for counting occurrences with an array, so the judge inspects your source code and forbids the C/C++ standard library associative containers: set, multiset, map, multimap, unordered_set, unordered_multiset, unordered_map, and unordered_multimap. Violating this restriction gives Wrong Answer with the feedback message 語法限制未通過.

The following sample program is too slow and only passes smaller tests.

#include<iostream>
using namespace std;
const int MAX_N = 200000;
int main() {
    int a[MAX_N];
    int N;
    cin >> N;
    for(int i = 0; i < N; i++) cin >> a[i];
    int Q;
    cin >> Q;
    while(Q--) {
        int b;
        cin >> b;
        int ans = 0;
        for(int i = 0; i < N; i++) ans += (a[i] == b);
        cout << ans << endl;
    }
    return 0;
}

Input

The first line contains a positive integer \(N\). The second line contains \(N\) positive integers \(a_1, a_2, \ldots, a_N\).

The third line contains a positive integer \(Q\). The fourth line contains \(Q\) positive integers \(b_1, b_2, \ldots, b_Q\).

Constraints

• \(1 \le N \le 2 \times 10^5\)
• \(1 \le a_i \le 10^6\)
• \(1 \le Q \le 2 \times 10^5\)
• \(1 \le b_i \le 10^9\)

Output

Print \(Q\) lines; the \(i\)-th line should contain the answer for the \(i\)-th query.

Scoring

There are three subtasks. Each subtask contains multiple test cases, and you earn the subtask's score only if you solve all of its tests.

• Subtask \(1\) (2 points): \(N, Q \le 5000\), \(b_i \le 10^6\).
• Subtask \(2\) (2 points): \(b_i \le 10^6\).
• Subtask \(3\) (1 point): no additional constraints.

Sample Input

5
1 3 1 4 520
7
1 2 3 4 100000 1000000000 7

Sample Output

2
0
1
1
0
0
0

Sample Explanation

\(1\) occurs twice in the sequence, \(3\) and \(4\) occur once each, and none of the other queried values occur at all, so the answers are \(2, 0, 1, 1, 0, 0, 0\).

The time limit is very tight. To pass the problem, enable fast I/O before reading anything:

cin.tie(0);
ios_base::sync_with_stdio(false);

Always use \n for newlines; using endl will also be too slow.