USACO

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.

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:

SAMPLE OUTPUT:

Problem credits: Nick Wu

Contest has ended. No further submissions allowed.