P4587 [FJOI2016] 神秘数

一个可重复数字集合 $S$ 的神秘数定义为最小的不能被 $S$ 的子集的和表示的正整数。例如 $S=\{1,1,1,4,13\}$，有：$1 = 1$，$2 = 1+1$，$3 = 1+1+1$，$4 = 4$，$5 = 4+1$，$6 = 4+1+1$，$7 = 4+1+1+1$。 $8$ 无法表示为集合 $S$ 的子集的和，故集合 $S$ 的神秘数为 $8$。 现给定长度为 $n$ 的**正整数**序列 $a$，$m$ 次询问，每次询问包含两个参数 $l,r$，你需要求出由 $a_l,a_{l+1},\cdots,a_r$ 所组成的可重集合的神秘数。

无

无

对于 $100\%$ 的数据点，$1\le n,m\le {10}^5$，$\sum a\le {10}^9$。