配点 : 100 点
問題文
长度 n\geq 2 非负整数序列 关于 a=(a_1,a_2,\ldots,a_n) , 将f(a) 定义为以下值:
- 执行以下操作 a 的所有元素
执行此操作所需的最少操作数(如果可以等于 0 )。如果你不能
满足 -1。
- 1\leq i\leq n,1\leq j\leq n,|i-j|=1 的整数 选择 i,j 。 替换为a_i 的 a_i\operatorname{AND}a_j 。
长度 N 非负整数序列 关于 A=(A_1,A_2,\ldots,A_N) 。Q 查询。 第
i 个查询是一个整数 查找 L_i,R_i ,所以f((A_{L_i},A_{L_i+1},\ldots,A_{R_i})) 。
AND 定义 对于
非負整数 x,y ,按位与 x\operatorname{AND}y 定义如下。- x\operatorname{AND}y 的 2 当用基本符号表示时 2^k 中的位数为 两个x 和 y 的2 当用基本符号表示时 2^k 数字都是 如果 1 如果 1 如果没有 0。
制約
- 2\leq N\leq 2\times 10^5
- 0\leq A_i\lt 2^{30}
- 1\leq Q\leq 2\times 10^5
- 1\leq L_i\lt R_i\leq N
入力
输入是按以下格式从标准输入给出的。 请按降序输出
N A_1 A_2 \ldots A_N Q L_1 R_1 L_2 R_2 \vdots L_Q R_Q
出力
请输出每个查询获得的值,以换行符分隔。 在第
入力例 1
3 5 6 11 2 1 3 2 3
出力例 1
4 -1
1 个查询中,a=(5,6,11) 作为 输出 f(a) 的值。 如果执行操作使其变为a 是 它可能以 (5,6,11)\rightarrow(5,4,11)\rightarrow(5,0,11)\rightarrow(5,0,0)\rightarrow(0,0,0) ,4 操作 a 的所有元素 可以等于 0 。 可以证明不存在少于4 次的操作程序,所以 输出f(a)=4 。
2 个查询中,a=(6,11) 作为 输出 f(a) 的值。无论你如何操作 我们可以证明它不能等于 a 的所有元素 执行此操作所需的最少操作数(如果可以等于 0 ,所以f(a)=-1 。
入力例 2
10 1017 40 583 310 485 428 726 123 143 962 10 2 3 2 10 3 10 5 8 5 6 5 6 3 8 6 7 1 9 1 9
出力例 2
2 9 9 5 -1 -1 7 -1 9 9