1426: 七曜与位运算

与 & 运算是计算机科学里面非常常见的一种运算, 在一次课后练习里面七曜遇到了这样一道题：

给出长度为 $n$ 的数组 $a$, 定义 $f(l,k)$ 为 $a_{l}$ & $ a_{l+1}$ & $a_{l+2}$ & ... & $a_{r}$, 给定 $l,k$ ，输出最大的使 $k \leq f(l,r)$ 的 $r$.

如果没有合法的 $r$  ，输出 $-1$

与 & 运算的定义为：

按位与处理两个二进制数，两个相应的二进位都为1，该位的结果值才为1，否则为0.

例如 $5_{(10)}$ 的二进制表示为 $101_{(2)}$， $2_{(10)}$ 的二进制表示为 $10_{(2)}$, 他们两个的与运算的值为 0

第一行包含一个整数 $n$.

第二行包含 $n$ 个整数$a_i$.

第三行包含一个整数 $q$.

接下来 $q$ 行，每行包含两个整数 $l,k$.

数据范围：

$1 \leq n \leq 2*10^5$.

$1 \leq a_i \leq 10^9$.

$1 \leq q \leq 10^5$.

$1 \leq l \leq n$.

$1 \leq k \leq 10^9$.

6
1 1 4 5 1 4
2
1 2
4 3

-1
4 

对于第一次询问，当 $l=1$ 时，不存在有效的 $r$ 使得 $k \leq f(l,r)$, 所以输出 $-1$.

对于第二次询问, 当 $l=4$ 时，只存在 $r=4$ 满足题目条件.