Challenge: How Many in Range?

Lab C++ Intermediate 20 points

Read exam scores (not sorted) and q questions lo hi. For each, print how many scores are between lo and hi (inclusive). Sort once, then use lower_bound/upper_bound.

Input

Line 1: n. Line 2: n scores. Line 3: q. Then q lines lo hi.

Output

One count per question.

Example

Input

6
50 90 70 60 90 30
3
60 90
0 40
91 100

Output

4
1
0

Sample input available Sample output available

Editor

C++

Hints

Sort once.

Count = upper_bound(hi) - lower_bound(lo).

Solution explanation

O(n log n) to sort, then O(log n) per question.

Show solution

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

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int& x : v) cin >> x;
    sort(v.begin(), v.end());
    int q;
    cin >> q;
    while (q--) {
        int lo, hi;
        cin >> lo >> hi;
        cout << upper_bound(v.begin(), v.end(), hi) - lower_bound(v.begin(), v.end(), lo) << endl;
    }
    return 0;
}

Output

Answer