C-牛牛的凑数游戏_2020牛客NOIP赛前集训营-提高组（第一场）

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

对于一个多重数集 ${S}$ ，对于一非负整数 ${x}$ ，若存在 $S' \subseteq S$ 且 ${S'}$ 中所有数字之和恰好等于 ${x}$ ，则说 ${S}$ 可以表示 ${x}$ 。
显然对于任意的多重数集都可以表示0，因为空集是所有集合的子集。
牛牛定义集合 ${S}$ 的最小不能表示数为，一个最小的非负整数 ${x}$ ， ${S}$ 不能表示 ${x}$ 。
举个例子来说，例如 ${S=\{1,2,3,8,9\}}$ ，那么集合 ${S}$ 的最小不能表示数就为7。
因为子集 ${\{\}}$ 的和为0，子集 ${\{1\}}$ 的和为1，子集 ${\{2\}}$ 的和为2，子集 ${\{1,2\}}$ 的和为3，子集 ${\{1,3\}}$ 的和为4，子集 ${\{2,3\}}$ 的和为5，子集 ${\{1,2,3\}}$ 的和为6。
但是无法找到子集权值和恰好为7的子集，所以7无法表示。
现在有一个长度大小为n的正整数数组，牛牛每次选择一个区间 ${[l,r]}$ ，他想要知道假定给出的多重数集为 $\{a_l,a_{l+1}...a_{r}\}$ 时，该集合的最小不能表示数是多少。

输入描述:

第一行输入两个正整数n,m。
接下来一行输入n个正整数表示输入的正整数数组。
接下来m行，每行输入两个正整数l,r表示查询的区间。

输出描述:

对于每一个查询，输出最小不能表示数

示例1

输入

复制

8 6
1 2 3 4 5 17 1 99
1 5
2 5
1 6
1 7
1 8
3 8

输出

复制

备注:

对于前10%的测试数据，保证
对于前20%的测试数据，保证
对于另10%的测试数据，保证输入的单调非降
对于另10%的测试数据，保证输入的为2的非负整数幂。
对于100%的测试数据，保证