Challenge: How Many in Range?

Lab Python Intermediate 20 points

Read a list of exam scores (not sorted) and then q questions lo hi. For each, print how many scores are between lo and hi (both included). Sort once, then use bisect for each question.

Input

Line 1: whole numbers. Line 2: q. Then q lines lo hi.

Output

One count per question.

Example

Input

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

Output

4
1
0

Sample input available Sample output available

Editor

Python

Hints

Sort the scores once.

bisect_left(a, lo) is the first index with a value ≥ lo.

bisect_right(a, hi) is just after the last value ≤ hi. Subtract the two.

Solution explanation

Sorting is O(n log n) once; then each question is O(log n).

Show solution

from bisect import bisect_left, bisect_right
scores = sorted(map(int, input().split()))
q = int(input())
for _ in range(q):
    lo, hi = map(int, input().split())
    print(bisect_right(scores, hi) - bisect_left(scores, lo))

Output

Answer