CF1189C Candies!

考虑一个长度为 $2^k$ 的序列 $[a_1,a_2,...,a_{2^k}]\ (0 \leq a_i \leq 9)$ 。我们对这个序列进行下列操作： 每次选中 $(a_{2i+1},a_{2i}) (0\leq i < 2^{k-1})$ ，共$2^{k-1}$对数字，若$a_{2i+1}+a_{2i}\ge 10$，你就能获得一颗糖果！ ，之后将每一个$(a_{2i+1}+a_{2i}) \mod 10$ 按 $i$ 从小到大重新写成一排，形成一个新的序列，长度为$2^{k-1}$ 我们不断执行这个操作直到序列的长度变为 $1$ 。我们用$f[a_1,a_2,...,a_k]$表示我们对序列$[a_1,a_2,...,a_k]$不断进行操作，最终一共获得的糖果。 举个栗子：序列为$[8,7,3,1,7,0,9,4]$ 第一步之后序列变为$[5,4,7,3]$，因为$8+7\ge 10 ,9+4 \ge 10$ 所以获得 $2$ 颗糖果 第二步之后序列变为$[9,0]$，因为$7+4 \ge 10$ 所以获得 $1$ 颗糖果 第三步之后序列变为$[9]$ 所以 $f([8,7,3,1,7,0,9,4]) = 3$，因为我们一共得到 $3$ 颗糖果 所以现在你有一个长度为 $n$ 的序列 $s_1,s_2,...,s_n$ ，给你 $q$ 组询问，每一次询问一个长度为 $2$ 的整数次幂的区间 $[l_i,r_i]$，请输出 $f([s_{l_i},s_{l_{i+1}},...,s_{r_i}])$ $f([7,3,1,7])=1$，因为 $[7,3,1,7] \rightarrow [0,8] \rightarrow [8]$ ，其中$7 + 3 \ge 10$ 所以只获得 $1$ 个糖果 $f([9])=0$，因为我们不需要进行操作。

第一行为一个整数 $n(1\leq n \leq 10^5)$，表示序列的长度 第二行为长度为 $n$ 的序列 $s[1...n] ,(0\leq s_i \leq 9)$ 第三行为一个整数 $q(1\leq q \leq 10^5)$ 表示询问个数 此后 $q$ 行每一行为两个整数 $l_i,r_i$，表示第 $i$ 个询问。保证 $r_i - l_i + 1$ 是 $2$ 的整数次幂

总共 $q$ 行，第 $i$ 行为第 $i$ 个询问的结果

The first example illustrates an example from the statement. $ f([7, 3, 1, 7]) = 1 $ : sequence of operations is $ [7, 3, 1, 7] \to [(7 + 3)\bmod 10, (1 + 7)\bmod 10] $ $ = $ $ [0, 8] $ and one candy as $ 7 + 3 \ge 10 $ $ \to $ $ [(0 + 8) \bmod 10] $ $ = $ $ [8] $ , so we get only $ 1 $ candy. $ f([9]) = 0 $ as we don't perform operations with it.