Counting Haybales

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

Medium4SortingBinary searchArrayPrefix sumInterviewNo attempts yetTime limit2sMemory limit512 MB

Description

Examples5

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.