3629: 牛牛的凑数游戏(第一轮03)

对于一个多重数集S， 对于一非负整数x， 若存在S ⊆ 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]，他想要知 道假定给出的多重数集为{al, al+1  … ar }时，该集合的最小不能表示数是多少。

第一行输入两个正整数 n,m。

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

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

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

16
1
16
34
34
2