### Vincent Massey SS - 2014 Senior Contest #1

## Problem B: Lil' Jami

Lil' Jami is playing with a set of `N` cups numbered 0, 1, …, `N`−1 and an infinite number of stones. Each cup initially has 0 stones in it. Since he has an infinite amount of free time, Lil' Jami plays a game where he repeatedly adds a stone to a cup. He does this `k` times.

Following this, there will be `Q` queries (1 ≤ `Q` ≤ 1,000,000) of the form "`a b`

" (0 ≤ `a` ≤ `b` < `N`). For each query, find the sum of the stones in cups numbered `a`, `a`+1, …, `b`−1, `b`.

### Input Format

The first line will contain the integers `N` and `K` (1 ≤ `N`, `K` ≤ 1,000,000) separated by a space.

The next `K` lines will each contain a single integer `k _{i}` (0 ≤

`k`<

_{i}`N`) meaning to add a stone to the cup with index

`k`(for 0 ≤

_{i}`i`<

`N`).

The next line will contain the single integer

`Q`.

The next

`Q`lines will contain two space-separated integers

`a`and

`b`.

### Output Format

For each query, print the sum of the number of stones in each of the cups in the range [`a`, `b`], inclusive.

### Sample Input

5 3 1 1 2 2 0 2 2 4

### Sample Output

3 1

All Submissions

Best Solutions

**Point Value:** 7

**Time Limit:** 3.00s

**Memory Limit:** 16M

**Added:** Nov 04, 2014

**Author:** thorthugnasty

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

xeonon Jul 20, 2019 - 8:54:25 pm UTC Data structure?magicalsoupon Jul 21, 2019 - 1:25:56 am UTC Re: Data structure?hockeyboyjgon Apr 16, 2015 - 9:32:47 pm UTC helpjargonon Apr 17, 2015 - 3:14:44 am UTC Re: helpjeffreyxiaoon Nov 04, 2014 - 3:52:28 am UTC Impossible for Java?Nvm... Over complicated the question

FatalEagleon Nov 04, 2014 - 4:04:14 am UTC Re: Impossible for Java?Butaneon Nov 04, 2014 - 4:07:20 am UTC Re: Impossible for Java?RaresBon Nov 04, 2014 - 4:42:35 am UTC Re: Impossible for Java?quantumon Nov 04, 2014 - 4:05:44 pm UTC Re: Impossible for Java?RaresBon Nov 04, 2014 - 11:00:49 pm UTC Re: Impossible for Java?