Counting Haybales

Interview

Time limit2sMemory limit512 MB

Summary

Given N distinct haybale positions and Q interval queries, count how many positions fall inside each inclusive range [A, B].

Level: Medium4 of 10
Topics: Sorting, Binary search, Array, Prefix sum
Solved: No attempts yet

Problem

Farmer John placed his $N$ haybales ( $1 \le N \le 100\,000$ ) at various points along the one-dimensional road that runs across his farm. To confirm that the spacing is right, he needs answers to $Q$ queries ( $1 \le Q \le 100\,000$ ). Each query asks how many haybales lie within a given interval of the road.

Input

The first line contains $N$ and $Q$ .

The second line contains $N$ distinct integers, each in the range $0$ to $1\,000\,000\,000$ . A haybale sits at each of those positions.

Each of the next $Q$ lines contains two integers $A$ and $B$ ( $0 \le A \le B \le 1\,000\,000\,000$ ), asking for the number of haybales whose position is between $A$ and $B$ , inclusive.

Output

Print $Q$ lines. For each query, in input order, print the number of haybales in its interval on its own line.

Examples5

Example 1

Input

Expected output

Example 2
Input
```
1 1
0
0 0
```
Expected output
```
1
```

Example 3

Input

1 3
1000000000
0 999999999
1000000000 1000000000
0 1000000000

Expected output

0
1
1

Example 4

Input

5 8
0 2 4 6 1000000000
0 0
1 1
2 2
3 3
6 6
999999999 999999999
1000000000 1000000000
0 1000000000

Expected output

Example 5

Input

6 5
10 20 30 40 50 60
0 9
61 1000000000
11 19
10 60
35 45

Expected output