lower_bound & upper_bound

Lab C++ Intermediate 20 points

Read a sorted vector and q queries. For each query print how many elements are < it and how many equal it, using lower_bound and upper_bound.

Input

n, the sorted integers, q, then q queries.

Output

q lines: less equal

Example

Input

7
1 2 2 2 5 7 9
4
2
6
0
10

Output

Sample input available Sample output available

Editor

C++

Hints

lower_bound: first element >= x. upper_bound: first element > x.

Solution explanation

Both run in O(log n) on sorted data.

Show solution

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, q;
    cin >> n;
    vector<int> v(n);
    for (int &x : v) cin >> x;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int x;
        cin >> x;
        auto lo = lower_bound(v.begin(), v.end(), x);
        auto hi = upper_bound(v.begin(), v.end(), x);
        cout << lo - v.begin() << " " << hi - lo << "\n";
    }
    return 0;
}

Output

Answer