B - AND Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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