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.

Problem credits: Nick Wu

Problem credits: Nick Wu

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.

You should write \(Q\) lines of output. For each query, output the number of
haybales in its respective interval.

riseoj 작성

출처 올림피아드 > USACO > 2016-2017 > December > Silver