Description

著名博学家尼古拉·哥白尼于 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}}$$

他会先插入括号使其成为良好括号化表达式$\text{*}$。例如，表达式 $2^{5}+2^{4}+2^{4}+2^{4}+2^{5}$ 可以通过插入括号变为 $((2^{5}+2^{4})+(2^{4}+(2^{4}+2^{5})))$。最后，他按照上述方式计算这个良好括号化表达式的结果。注意，计算结果可能因括号插入方式的不同而有所变化。例如，以下是两种可能的计算方式：

$$((2^{5}+2^{4})+2^{4})+(2^{4}+2^{5}))=((2^{6}+2^{4})+2^{6})=(2^{7}+2^{6})=2^{8} \\((2^{5}+(2^{4}+2^{4}))+(2^{4}+2^{5}))=((2^{5}+2^{5})+2^{6})=(2^{6}+2^{6})=2^{7}$$

哥白尼笔记本的第一页仅包含一个称为主表达式的表达式 $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$。

你不确定这些片段的含义，但怀疑应该为每个片段计算其可能的最小结果（按照上述方式计算）。注意，每个片段是独立于其他片段计算的。

$\text{*}$关于“良好括号化表达式”的形式化定义如下：对于任意非负整数 $a$，$2^{a}$ 是一个良好括号化表达式；如果 $E_{1}$ 和 $E_{2}$ 都是良好括号化表达式，那么 $(E_{1} + E_{2})$ 也是良好括号化表达式。除此之外没有其他形式的良好括号化表达式。

Input Format

第一行包含两个整数 $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 的幂次的片段。

Output Format

输出 $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

Hint

评分

子任务	限制条件	分值
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

翻译由 DeepSeek V3 完成