← 返回题目列表

AtCoder · pakencamp_2023_day3_b

B. 和

中文机器翻译题面 查看原题

配点 : 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。
例如,5\operatorname{AND}12=4 。 (2 采用基本符号 101\operatorname{AND}1100=100 。 )

制約

  • 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