## USACO 2016 December Contest, Silver

## Problem 1. Counting Haybales

Contest has ended.

**Log in to allow submissions in analysis mode**

Farmer John has just arranged his $N$ haybales ($1 \leq N \leq 100,000$) at
various points along the one-dimensional road running across his farm. To make
sure they are spaced out appropriately, please help him answer $Q$ queries
($1 \leq Q \leq 100,000$), each asking for the number of haybales within a
specific interval along the road.

Contest has ended. No further submissions allowed.
#### INPUT FORMAT (file haybales.in):

The first line contains $N$ and $Q$.The next line contains $N$ distinct integers, each in the range $0 \ldots 1,000,000,000$, indicating that there is a haybale at each of those locations.

Each of the next $Q$ lines contains two integers $A$ and $B$ ($0 \leq A \leq B \leq 1,000,000,000$) giving a query for the number of haybales between $A$ and $B$, inclusive.

#### OUTPUT FORMAT (file haybales.out):

You should write $Q$ lines of output. For each query, output the number of haybales in its respective interval.#### SAMPLE INPUT:

4 6 3 2 7 5 2 3 2 4 2 5 2 7 4 6 8 10

#### SAMPLE OUTPUT:

2 2 3 4 1 0

Problem credits: Nick Wu