题目描述
一个可重复数字集合 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,你需要求出由 al,al+1,⋯,ar 所组成的可重集合的神秘数。
输入格式
第一行一个整数 n,表示数字个数。
第二行 n 个正整数,从 1 编号。
第三行一个整数 m,表示询问个数。
输出格式
对于每个询问,输出一行对应的答案。
提示
对于 100% 的数据点,1≤n,m≤105,∑a≤109。