题目描述

著名的博学家尼古拉·哥白尼于 15 世纪出生并成长于托伦。考古学家最近发现了他的笔记本，得知他喜欢用 $2$ 的幂来存储大数字。特别是，当他计算两个 $2$ 的幂之和时：

$$2^a + 2^b$$

哥白尼会先计算结果，然后将结果向上取整到最近的 $2$ 的幂。也就是说，他会将 $2^a + 2^b$ 计算为 $2^{\max(a, b)+1}$。对于更长的表达式，例如：

$$2^{b_1} + 2^{b_2} + \ldots + 2^{b_k}$$

他会先插入括号，使其成为一个格式规范的括号表达式*。例如，表达式 $2^5 + 2^4 + 2^4 + 2^4 + 2^5$ 可以被括号化为 $\left(\left(2^5 + 2^4\right) + \left(2^4 + \left(2^4 + 2^5\right)\right)\right)$。然后，他按照上述规则计算这个括号表达式的结果。需要注意的是，结果可能会因括号的插入方式不同而变化。例如，以下是计算 $2^5 + 2^4 + 2^4 + 2^4 + 2^5$ 的两种可能方式：

$$\begin{aligned} & \left(\left(\left(2^5 + 2^4\right) + 2^4\right) + \left(2^4 + 2^5\right)\right) = \left(\left(2^6 + 2^4\right) + 2^6\right) = \left(2^7 + 2^6\right) = 2^8 \\ & \left(\left(2^5 + \left(2^4 + 2^4\right)\right) + \left(2^4 + 2^5\right)\right) = \left(\left(2^5 + 2^5\right) + 2^6\right) = \left(2^6 + 2^6\right) = 2^7 \end{aligned} $$

哥白尼笔记本的第一页仅包含一个主表达式 $2^{a_1} + 2^{a_2} + \ldots + 2^{a_n}$，称为主表达式。后续页面则引用了主表达式的片段，形式为 $2^{a_\ell} + 2^{a_{\ell+1}} + \ldots + 2^{a_r}$，其中 $1 \leq \ell \leq r \leq n$。

你还不确定这些片段的含义，但你猜测需要为每个片段计算按照上述规则求值时所能得到的最小结果。注意，每个片段的求值是相互独立的。

输入格式

第一行包含两个整数 $n$ 和 $q$ $(1 \leq n, q \leq 300000)$，分别表示笔记本第一页主表达式的长度和查询次数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(0 \leq a_i \leq 10^6)$，其中第 $i$ 个整数 $a_i$ 表示主表达式中第 $i$ 个 $2$ 的幂的指数。

接下来的 $q$ 行描述查询。每行包含两个整数 $\ell$ 和 $r$ $(1 \leq \ell \leq r \leq n)$，表示主表达式的一个片段，从第 $\ell$ 个 $2$ 的幂开始，到第 $r$ 个 $2$ 的幂结束。

输出格式

输出 $q$ 行。第 $i$ 行应包含第 $i$ 个查询描述的片段按照上述规则求值时所能得到的最小结果，仅输出对应 $2$ 的幂的指数。

8 4
2 4 2 5 4 4 4 5
4 8
1 4
2 5
1 7

7
7
7
8

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务编号	附加限制	分值
$1$	$n \leq 8, q \leq 10$	$6$
$2$	$n \leq 200$	$8$
$3$	$n, q \leq 2000$	$23$
$4$	$a_i \leq 20$	$22$
$5$	无附加限制	$41$