Count numbers in a range

Read n numbers in increasing order (they may repeat), then q questions lo hi. For each question, print how many of the numbers are between lo and hi, inclusive. Use binary search, not a loop over the whole array.

What to build

A program that answers range-count questions on sorted numbers with binary search.

Requirements

• Write a lower_bound function that returns the first index whose value is at least x.
• Answer each question with two calls to that function.
• Do not loop over the whole array for each question.

Input

The first line has n (1 ≤ n ≤ 1000) and the second line the n numbers in increasing order. The third line has q (1 ≤ q ≤ 1000). Each of the next q lines has lo and hi (lo ≤ hi).

Output

One line per question: the count.

Constraints

1 ≤ n ≤ 1000 and 1 ≤ q ≤ 1000, with lo ≤ hi in every question.

Example

Input:

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

Output:

3
6
0

Why it works

Sorted numbers from lo to hi sit side by side. The block starts at lower_bound(lo) and ends just before lower_bound(hi + 1), so the difference is its length.

Examples

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

3
6
0

1
4
2
4 4
5 9

1
0

Hints

Solution

#include <stdio.h>

int lower_bound(int a[], int n, int key) {   // the first index with a[i] >= key
    int lo = 0, hi = n;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < key) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

int main(void) {
    int n, q;
    int a[1000];
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        int lo, hi;
        scanf("%d %d", &lo, &hi);
        printf("%d\n", lower_bound(a, n, hi + 1) - lower_bound(a, n, lo));
    }
    return 0;
}

Lesson: Binary search →