영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
시간 제한 1초 · 메모리 제한 512 MB
Problem
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
- 1 ≤ n, q ≤ 2 · 10^5
- 1 ≤ x_i ≤ 10^9
- 1 ≤ a ≤ b ≤ n
Example
Explanation: First you can use coins [9,1,2], then coins [2] and finally coins [2,9,1,2,7].
예제
예제 1
5 3 2 9 1 2 7 2 4 4 4 1 5
4 1 6