AT_pakencamp_2023_day3_b AND

長さ $ 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 $ となります。）

入力は以下の形式で標準入力から与えられます。 > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ Q $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \vdots $ $ L_Q $ $ R_Q $

各クエリで求めた値を改行区切りで出力してください。

### Sample Explanation 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 $ となります。 ### Constraints - $ 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 $