对于长度为 $$$m$$$ ($$$b_i \geq 2$$$) 的数组 $$$b=[b_1,b_2,\ldots,b_m]$$$,请考虑 Poby 和 Rekkles 玩的以下两人游戏。
- 玩家轮流行动,波比先行动。
- 轮到 Poby 时,他必须选择一个元素 $$$x \ge 2$$$ 并将其替换为 $$$\left\lfloor \frac{x}{2} \right\rfloor$$$。换句话说,他选择 $$$i$$$ ($$$1 \leq i \leq m$$$) 使得 $$$b_i \ge 2$$$,然后 $$$b_i := \left\lfloor \frac{b_i}{2} \right\rfloor$$$。
- 在 Rekkles 的回合中,他必须从数组 $$$b$$$ 中选择一个元素 $$$x \ge 2$$$ 并将其替换为 $$$x+1$$$。换句话说,他选择 $$$i$$$ ($$$1 \leq i \leq m$$$) 使得 $$$b_i \ge 2$$$,然后执行 $$$b_i := b_i+1$$$。
一旦数组$$$b$$$中的所有元素都等于$$$1$$$,游戏结束。
定义 分数 游戏的 作为 Poby 的移动次数。 Poby 的目标是尽量减少 分数 游戏的,而 Rekkles 的目标是最大化 分数 游戏的.
然后, 值 数组$$$b$$$的 是双方都发挥最佳状态时的游戏得分。
给定一个整数数组 $$$a$$$,长度为 $$$n$$$ ($$$a_i \ge 2$$$)。
回答 $$$q$$$ 独立查询。在每个查询中,您都会得到一个范围 $$$1 \leq l \leq r \leq n$$$ 并且必须找到 数组 $$$[a_l, a_{l+1}, \ldots, a_r]$$$ 的 值 数组$$$b$$$的 。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 250\,000$$$) - 数组的长度和查询的数量。
下一行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$2 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的元素。
然后是 $$$q$$$ 行。其中第 $$$j$$$ 包含两个整数 $$$l_j$$$ 和 $$$r_j$$$ ($$$1 \le l_j \le r_j \le n$$$) - 第 $$$i$$$ 查询的子数组范围。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$250\,000$$$。
保证所有测试用例的 $$$q$$$ 总和不超过 $$$250\,000$$$。
输出
对于每个测试用例,输出 $$$q$$$ 行。第 $$$i$$$ 行应包含一个整数,表示第 $$$i$$$ 查询的答案。
示例
输入复制
25 54 3 2 5 61 11 22 43 51 510 1314 159 265 358 979 323 846 264 338 3271 10
输出复制
23561091
注意
第一个测试用例的解释,第一个查询 (1 1):
子数组是$$$[4]$$$。
- Poby:$$$4\to \left\lfloor \tfrac{4}{2}\right\rfloor=2$$$。该数组是$$$[2]$$$。
- Rekkles:$$$2\到 3$$$。该数组是$$$[3]$$$。
- Poby:$$$3\to \left\lfloor \tfrac{3}{2}\right\rfloor=1$$$。数组是$$$[1]$$$,所以游戏结束。
可以证明该策略对于双方玩家都是最优的。因此,数组$$$[4]$$$的值为$$$2$$$。
第一个测试用例的解释,第二个查询 (1 2):
子数组是$$$[4,3]$$$。
- Poby:$$$3\to \left\lfloor \tfrac{3}{2}\right\rfloor=1$$$。该数组是$$$[4,1]$$$。
- Rekkles:$$$4\到 5$$$。该数组是$$$[5,1]$$$。
- Poby:$$$5\to \left\lfloor \tfrac{5}{2}\right\rfloor=2$$$。该数组是$$$[2,1]$$$。
- Rekkles:$$$2\到 3$$$。该数组是$$$[3,1]$$$。
- Poby:$$$3\to \left\lfloor \tfrac{3}{2}\right\rfloor=1$$$。数组是$$$[1,1]$$$,所以游戏结束。
可以证明该策略对于双方玩家都是最优的。因此,数组$$$[4,3]$$$的值为$$$3$$$。