T277379 牛牛的凑数游戏

牛牛十分聪明，他想问你有关一堆数的问题

对于一个多重数集$S$，对于一非负整数$x$，若存在$S \in 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$个正整数$a_{i}$表示输入的正整数数组。 接下来m行，每行输入两个正整数$l,r$表示查询的区间

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

对于前10%的测试数据，保证$1\le n,m\le 10 ,1\le a_{i}\le 100$ 对于前20%的测试数据，保证$1\le n,m\le 500$ 对于另10%的测试数据，保证输入的$a_{i}$单调非降 对于另10%的测试数据，保证输入的$a_{i}$为2的非负整数幂。 对于100%的测试数据，保证$1\le n,m\le 10^5,1\le a_{i} \le 10^9 ,1\le l\le r \le n$