Mysterious Number

You are given a sequence of positive integers a of length n and m queries. Each query provides two integers l and r and asks to compute the mysterious number for the multiset

$$S = \{a_l, a_{l+1}, \cdots, a_r\}$$

The mysterious number of a multiset S is defined as the smallest positive integer that cannot be represented as the sum of a subset of S. For example, consider S = {1, 1, 1, 4, 13}. We can represent:

• $$1 = 1$$
• $$2 = 1+1$$
• $$3 = 1+1+1$$
• $$4 = 4$$
• $$5 = 4+1$$
• $$6 = 4+1+1$$
• $$7 = 4+1+1+1$$

Since 8 cannot be represented as the sum of any subset of S, its mysterious number is 8.

For each query, compute the mysterious number for the subarray a[l...r].

inputFormat

The first line contains two integers n and m separated by a space, indicating the length of the sequence and the number of queries, respectively.

The second line contains n positive integers: a₁, a₂, ..., a_n.

Each of the next m lines contains two integers l and r (1-indexed), representing a query.

outputFormat

For each query, output a single line containing the mysterious number corresponding to the subarray a[l...r].

sample

5 2
1 1 1 4 13
1 5
2 4

8
3