每日思维 / 构造

考虑一个长度为 2^k 的数字序列 [a_1, a_2, …, a_{2^k}]。我们对它执行以下操作：对于 0≤ i < 2^{k-1}，将数对 (a_{2i+1}, a_{2i+2}) 替换为 (a_{2i+1} + a_{2i+2})\bmod 10。对于每个满足 a_{2i+1} + a_{2i+2}≥ 10 的 i，我们得到一颗糖果！结果，我们将得到一个长度为 2^{k-1} 的序列。
更不正式地说，我们将长度为 2^k 的序列划分成 2^{k-1} 个数对，每个数对由 2 个数字组成：第一个数对由第一个和第二个数字组成，第二个数对由第三个和第四个数字组成 …，最后一个数对由第 (2^k-1) 个和第 (2^k) 个数字组成。对于每个数对，如果其中数字之和至少为 10，我们就得到一颗糖果。之后，我们将每个数对中的数字替换为它们的和对 10 取模的余数（并且不改变数字的顺序）。
对结果数组执行此操作，直到其长度变为 1。令 f([a_1, a_2, …, a_{2^k}]) 表示在此过程中得到的糖果数。
例如：如果起始序列是 [8, 7, 3, 1, 7, 0, 9, 4]，那么：
第一次操作后，序列变为 [(8 + 7)\bmod 10, (3 + 1)\bmod 10, (7 + 0)\bmod 10, (9 + 4)\bmod 10] = [5, 4, 7, 3]，并且我们得到 2 颗糖果，因为 8 + 7 ≥ 10 且 9 + 4 ≥ 10。
第二次操作后，序列变为 [(5 + 4)\bmod 10, (7 + 3)\bmod 10] = [9, 0]，并且我们又得到一颗糖果，因为 7 + 3 ≥ 10。
最后一次操作后，序列变为 [(9 + 0) \bmod 10] = [9]。
因此，f([8, 7, 3, 1, 7, 0, 9, 4]) = 3，因为我们总共得到了 3 颗糖果。
给定一个长度为 n 的数字序列 s_1, s_2, … s_n。你必须回答 q 个形如 (l_i, r_i) 的查询，其中对于第 i 个查询，你必须输出 f([s_{l_i}, s_{l_i+1}, …, s_{r_i}])。保证 r_i-l_i+1 对某个非负整数 k 具有 2^k 的形式。

Polycarp 正在设计一个游戏的关卡。该关卡由数轴上的 n 条线段组成，其中第 i 条线段从坐标为 l_i 的点开始，到坐标为 r_i 的点结束。
玩家从坐标为 0 的点开始该关卡。在一次移动中，他们可以移动到距离不超过 k 的任意点。在第 i 次移动后，玩家必须落在第 i 条线段内，即落在坐标 x 满足 l_i ≤ x ≤ r_i 的位置。这意味着：
· 第一次移动后，他们必须在第一条线段内（从 l_1 到 r_1）；
· 第二次移动后，他们必须在第二条线段内（从 l_2 到 r_2）；
· ...
· 第 n 次移动后，他们必须在第 n 条线段内（从 l_n 到 r_n）。
如果玩家按照上述规则到达第 n 条线段，则关卡被视为完成。经过一番思考，Polycarp 意识到对于某些 k 值，不可能完成关卡。
Polycarp 不希望关卡太简单，因此他要求你确定能够完成关卡的最小整数 k。