P12430 [BalticOI 2025] Exponents

著名博学家尼古拉·哥白尼于 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})$ 也是良好括号化表达式。除此之外没有其他形式的良好括号化表达式。

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

### 评分 | 子任务 | 限制条件 | 分值 | | :---: | :---: | :---: | | 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 完成