Ticket Range Count

Problem

A theatre sold n tickets. The seat numbers on the tickets are already sorted from smallest to largest, and the same seat number can appear more than once because of re-issued tickets.

At the box office the manager fields q questions. Each question gives a range of seat numbers lo to hi, both included. For each question, report how many tickets have a seat number in that range.

Input

The first line has two integers n and q. The second line has n integers in non-decreasing order. Each of the next q lines has two integers lo and hi.

Output

For each question print one integer on its own line.

Constraints

• 1 ≤ n, q ≤ 50000
• 0 ≤ seat numbers ≤ 10⁹
• 0 ≤ lo ≤ hi ≤ 10⁹

Notes

In the first example the tickets are 1, 3, 3, 5, 8, 13. The range 3 to 5 holds the seats 3, 3 and 5, so the answer is 3. No ticket has seat 4, so the range 4 to 4 holds none. The range 0 to 100 holds all 6 tickets.