题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

给定一个长度为 $M$ 的正整数序列 $X_1, X_2, \dots, X_M$，我们希望将这个序列变为升序。一个序列 $X_1, X_2, \dots, X_M$ 是升序的，当且仅当对所有 $i$（$1 \leq i \leq M - 1$）满足 $X_i \leq X_{i+1}$。

为了将序列 $X$ 变为升序，可以对其应用如下操作任意次数（包括 $0$ 次）：

• 对于某个 $i$（$1 \leq i \leq M$），将 $X_i$ 乘以 $2$。

我们将通过最少的操作次数将 $X$ 变为升序时所需的操作次数记为 $f(X)$。

现在，给定一个长度为 $N$ 的正整数序列 $A_1, A_2, \dots, A_N$，以及 $Q$ 个查询。每个查询给出两个整数 $l$ 和 $r$，满足 $1 \leq l \leq r \leq N$。查询的目标是计算 $f(A_l, A_{l+1}, \dots, A_r)$，即将从 $A$ 中截取的子序列升序所需的最小操作次数。

请计算并输出每个查询的答案。

输入格式

第一行输入两个整数 $N$ 和 $Q$，用空格分隔。
第二行输入 $N$ 个整数 $A_1, A_2, \dots, A_N$，用空格分隔。
接下来的 $Q$ 行，每行输入两个整数 $l$ 和 $r$，表示一次查询。

输出格式

输出 $Q$ 行，第 $i$ 行输出第 $i$ 个查询的答案。

10 5
5 2 7 3 2 9 6 3 3 5
3 9
1 10
1 8
2 4
8 9

14
27
19
2
0

10 5
2 8 4 9 10 8 5 3 7 7
2 8
1 10
3 3
1 3
8 10

7
11
0
1
0

提示

约束条件

• 所有输入均为整数。
• $1 \leq N \leq 250\,000$
• $1 \leq Q \leq 250\,000$
• $1 \leq A_i \leq 10^9 \quad (1 \leq i \leq N)$
• 对所有查询满足 $1 \leq l \leq r \leq N$

子问题

1.（5 分）$N \leq 10\,000,\ Q \leq 10\,000$
2.（7 分）$N \leq 10\,000$
3.（28 分）所有查询满足 $r = N$
4.（10 分）对所有 $i$ 满足 $A_i \geq A_{i+1}$
5.（5 分）对所有 $i$ 满足 $A_i \leq 2$
6.（10 分）对所有 $i$ 存在非负整数 $k_i$ 使得 $A_i = 2^{k_i}$
7.（35 分）无额外限制条件

翻译由 ChatGPT-4o 完成