Can anyine solve this problem? [Problem Link](https://cses.fi/problemset/task/2184/)↵
↵
Time limit: 1.00 s↵
Memory limit: 512 MB↵
# Statement↵
You have n coins with positive integer values. The coins are numbered 1, 2, ...., n.↵
Your task is to process q queries of the form: "if you can use coins a ..... b, what is the smallest sum you cannot produce?"↵
# Input↵
The first input line has two integers n and q: the number of coins and queries.↵
The second line has n integers x_1, x_2, ......., x_n: the value of each coin.↵
Finally, there are q lines that describe the queries. Each line has two values a and b: you can use coins a .... b.↵
# Output↵
Print the answer for each query.↵
# Constraints↵
↵
* n , q <= 1e5↵
* x_i <= 1e9↵
* 1 <= a <= b <= n↵
↵
Example↵
Input:↵
5 3↵
2 9 1 2 7↵
2 4↵
4 4↵
1 5↵
↵
Output:↵
4↵
1↵
6 <br>↵
5 3 <br>↵
2 9 1 2 7 <br>↵
2 4 <br>↵
4 4 <br>↵
1 5 <br>↵
↵
Output: <br>↵
4 <br>↵
1 <br>↵
6 <br>↵
↵
Explanation: First you can use coins [9,1,2], then coins [2] and finally coins [2,9,1,2,7].↵
↵
Time limit: 1.00 s↵
Memory limit: 512 MB↵
# Statement↵
You have n coins with positive integer values. The coins are numbered 1, 2, ...., n.↵
Your task is to process q queries of the form: "if you can use coins a ..... b, what is the smallest sum you cannot produce?"↵
# Input↵
The first input line has two integers n and q: the number of coins and queries.↵
The second line has n integers x_1, x_2, ......., x_n: the value of each coin.↵
Finally, there are q lines that describe the queries. Each line has two values a and b: you can use coins a .... b.↵
# Output↵
Print the answer for each query.↵
# Constraints↵
↵
* n , q <= 1e5↵
* x_i <= 1e9↵
* 1 <= a <= b <= n↵
↵
Example↵
Input:
5 3↵
2 9 1 2 7↵
2 4↵
4 4↵
1 5↵
↵
Output:↵
4↵
1↵
6
5 3 <br>↵
2 9 1 2 7 <br>↵
2 4 <br>↵
4 4 <br>↵
1 5 <br>↵
↵
Output: <br>↵
4 <br>↵
1 <br>↵
6 <br>↵
↵
Explanation: First you can use coins [9,1,2], then coins [2] and finally coins [2,9,1,2,7].↵
