CF878E Numbers on the blackboard

黑板上写有 $n$ 个整数。不久之后，Sasha 会来到黑板前，开始进行以下操作：设 $x$ 和 $y$ 是两个相邻的数字（$x$ 在前，$y$ 在后），他可以将它们移除，并把 $x+2y$ 写在这两个数的位置上。Sasha 会不断进行这样的操作，直到只剩下一个数字。他喜欢大数，并且会让结果尽可能大。 Nikita 想要在 Sasha 来之前擦掉一些数字。他有 $q$ 种方案，在第 $i$ 种方案中，他会擦去第 $l_{i}$ 个数字左边的所有数字和第 $r_{i}$ 个数字右边的所有数字，也就是说，只保留从第 $l_{i}$ 个到第 $r_{i}$ 个（包含两端）之间的数字在黑板上。对于每一种方案，他都想知道，Sasha 最终能得到的最大数字是多少。由于结果可能非常大，请将其对 $10^{9}+7$ 取模后输出。

第一行包含两个整数 $n$ 和 $q$（$1 \leq n, q \leq 10^5$），表示黑板上的整数个数和 Nikita 的方案数。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^9 \leq a_i \leq 10^9$），表示黑板上的数列。 接下来的 $q$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \leq l_i \leq r_i \leq n$），描述 Nikita 的第 $i$ 种擦除方式。

对于每种方案，输出 Sasha 在该方案下最终得到的数字（对 $10^9+7$ 取模）。

在第二组样例中，Nikita 没有擦掉任何数字。Sasha 首先合并 $1$ 和 $2$ 得到 $5$，再合并 $5$ 和 $-3$ 得到 $-1$，$-1$ 对 $10^9+7$ 取模后为 $10^9 + 6$。 由 ChatGPT 5 翻译