考虑长度为 $$$2^k$$$ $$$[a_1, a_2, \ldots, a_{2^k}]$$$ 的数字序列。我们用它执行以下操作:将 $$$(a_{2i+1}, a_{2i+2})$$$ 替换为 $$$(a_{2i+1} + a_{2i+2})\bmod 10$$$ for $$$0\le i<2^{k-1}$$$。对于每 $$$i$$$ 其中 $$$a_{2i+1} + a_{2i+2}\ge 10$$$ 我们都会得到一颗糖果!结果,我们将得到长度为 $$$2^{k-1}$$$ 的序列。
不太正式,我们将长度 $$$2^k$$$ 的序列划分为 $$$2^{k-1}$$$ 对,每个对由 2 个数字组成:第一对由第一个和第二个数字组成,第二对由第三个和第四个 $$$\ldots$$$ 组成,最后一对由第 ($$$2^k-1$$$) 和第 ($$$2^k$$$) 个数字组成。对于每对数字总和至少为 $$$10$$$ 的配对,我们都会得到一颗糖果。之后,我们将每对数字替换为它们的总和除以 $$$10$$$ 的余数(并且不改变数字的顺序)。
对结果数组执行此操作,直到其长度变为 $$$1$$$。令 $$$f([a_1, a_2, \ldots, 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 \ge 10$$$ 和 $$$9 + 4 \ge 10$$$。
第二次操作后,序列变为 $$$[(5 + 4)\bmod 10, (7 + 3)\bmod 10]$$$ $$$=$$$ $$$[9, 0]$$$,我们又得到一颗糖果 $$$7 + 3 \ge 10$$$。
最终运算序列变为$$$[(9 + 0) \bmod 10]$$$ $$$=$$$ $$$[9]$$$。
因此,$$$f([8, 7, 3, 1, 7, 0, 9, 4]) = 3$$$,因为我们总共得到了 $$$3$$$ 糖果。
给你一个长度为 $$$n$$$ $$$s_1, s_2, \ldots s_n$$$ 的数字序列。您必须回答 $$$(l_i, r_i)$$$ 形式的 $$$q$$$ 查询,其中对于第 $$$i$$$ 个查询,您必须输出 $$$f([s_{l_i}, s_{l_i+1}, \ldots, s_{r_i}])$$$。对于某个非负整数 $$$k$$$,保证 $$$r_i-l_i+1$$$ 的形式为 $$$2^k$$$。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 序列的长度。
第二行包含 $$$n$$$ 数字 $$$s_1, s_2, \ldots, s_n$$$ ($$$0 \le s_i \le 9$$$)。
第三行包含一个整数 $$$q$$$ ($$$1 \le q \le 10^5$$$) — 查询数。
接下来的 $$$q$$$ 行包含两个整数 $$$l_i$$$、$$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — 第 $$$i$$$ 查询。保证 $$$r_i-l_i+1$$$ 是 $$$2$$$ 的非负整数幂。
输出
输出 $$$q$$$ 行,在第 $$$i$$$ 行中输出单个整数 — $$$f([s_{l_i}, s_{l_i + 1}, \ldots, s_{r_i}])$$$,回答第 $$$i$$$ 查询。
示例
输入 #1
8 8 7 3 1 7 0 9 4 3 1 8 2 5 7 7
输出 #1
3 1 0
输入 #2
6 0 1 2 3 3 5 3 1 2 1 4 3 6
输出 #2
0 0 1
注意
第一个示例说明了语句中的示例。
$$$f([7, 3, 1, 7]) = 1$$$:操作顺序为 $$$[7, 3, 1, 7] \to [(7 + 3)\bmod 10, (1 + 7)\bmod 10]$$$ $$$=$$$ $$$[0, 8]$$$ 和一颗糖果 $$$7 + 3 \ge 10$$$ $$$\to$$$ $$$[(0 + 8) \bmod 10]$$$ $$$=$$$ $$$[8]$$$,所以我们只得到$$$1$$$糖果。
$$$f([9]) = 0$$$ 因为我们不使用它执行操作。