ADACOINS – Ada and Coins Solution

0
25
ADACOINS – Ada and Coins Solution – Ada the Ladybug has several coins in her wallet. She is wondering, how many different values [sum of some subset of coins] is she able to make (in given range).

Input

The first line contains two integer numbers 1 ≤ N ≤ 104, 1 ≤ Q ≤ 5*105, the number of coins and number of queries.

The next line contains N integer numbers 1 ≤ Ai ≤ 105, the values of coins in Ada’s wallet.

Afterward, Q lines follow, each containing two integers 1 ≤ B ≤ E ≤ 105beginning and end of range, for which ada wants to know the answer

Output

For each query, output the number of distinct values Ada can generate in given range.

Read more:

LEAVE A REPLY

Please enter your comment!
Please enter your name here

This site uses Akismet to reduce spam. Learn how your comment data is processed.