CF1189C.Candies!

Consider a sequence of digits of length $2^k$ $[a_1, a_2, \ldots, a_{2^k}]$. We perform the following operation with it: replace pairs $(a_{2i+1}, a_{2i+2})$ with $(a_{2i+1} + a_{2i+2})\bmod 10$ for $0\le i \lt 2^{k-1}$. For every $i$ where $a_{2i+1} + a_{2i+2}\ge 10$ we get a candy! As a result, we will get a sequence of length $2^{k-1}$.

Less formally, we partition sequence of length $2^k$ into $2^{k-1}$ pairs, each consisting of 2 numbers: the first pair consists of the first and second numbers, the second of the third and fourth $\ldots$, the last pair consists of the ($2^k-1$)-th and ($2^k$)-th numbers. For every pair such that sum of numbers in it is at least $10$, we get a candy. After that, we replace every pair of numbers with a remainder of the division of their sum by $10$ (and don't change the order of the numbers).

Perform this operation with a resulting array until it becomes of length $1$. Let $f([a_1, a_2, \ldots, a_{2^k}])$ denote the number of candies we get in this process.

For example: if the starting sequence is $[8, 7, 3, 1, 7, 0, 9, 4]$ then:

After the first operation the sequence becomes $[(8 + 7)\bmod 10, (3 + 1)\bmod 10, (7 + 0)\bmod 10, (9 + 4)\bmod 10]$ $=$ $[5, 4, 7, 3]$, and we get $2$ candies as $8 + 7 \ge 10$ and $9 + 4 \ge 10$.

After the second operation the sequence becomes $[(5 + 4)\bmod 10, (7 + 3)\bmod 10]$ $=$ $[9, 0]$, and we get one more candy as $7 + 3 \ge 10$.

After the final operation sequence becomes $[(9 + 0) \bmod 10]$ $=$ $[9]$.

Therefore, $f([8, 7, 3, 1, 7, 0, 9, 4]) = 3$ as we got $3$ candies in total.

You are given a sequence of digits of length $n$ $s_1, s_2, \ldots s_n$. You have to answer $q$ queries of the form $(l_i, r_i)$, where for $i$-th query you have to output $f([s_{l_i}, s_{l_i+1}, \ldots, s_{r_i}])$. It is guaranteed that $r_i-l_i+1$ is of form $2^k$ for some nonnegative integer $k$.

考虑一个长度为 $2^k$ 的数字序列 $[a_1, a_2, \ldots, a_{2^k}]$。我们对其执行如下操作：对每个 $0\le i \lt 2^{k-1}$，将数对 $(a_{2i+1}, a_{2i+2})$ 替换为 $(a_{2i+1} + a_{2i+2})\bmod 10$；若对某个 $i$ 满足 $a_{2i+1} + a_{2i+2}\ge 10$，则获得一颗糖果！最终得到一个长度为 $2^{k-1}$ 的新序列。

更直观地讲，我们将长度为 $2^k$ 的序列划分为 $2^{k-1}$ 个二元组，每个组包含两个数字：第一个组由第 $1$ 个和第 $2$ 个数字组成，第二个组由第 $3$ 个和第 $4$ 个数字组成，……，最后一个组由第 $2^k-1$ 个和第 $2^k$ 个数字组成。对每个满足其两数之和 $\ge 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]$，再获得 $1$ 颗糖果（因为 $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$。你需要回答 $q$ 个查询，每个查询形如 $(l_i, r_i)$；对第 $i$ 个查询，需输出 $f([s_{l_i}, s_{l_i+1}, \ldots, s_{r_i}])$。保证对每个查询均有 $r_i-l_i+1 = 2^k$（其中 $k$ 为某个非负整数）。

The first line contains a single integer $n$ ($1 \le n \le 10^5$) — the length of the sequence.

The second line contains $n$ digits $s_1, s_2, \ldots, s_n$ ($0 \le s_i \le 9$).

The third line contains a single integer $q$ ($1 \le q \le 10^5$) — the number of queries.

Each of the next $q$ lines contains two integers $l_i$, $r_i$ ($1 \le l_i \le r_i \le n$) — $i$-th query. It is guaranteed that $r_i-l_i+1$ is a nonnegative integer power of $2$.

第一行包含一个整数 $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$。

Output $q$ lines, in $i$-th line output single integer — $f([s_{l_i}, s_{l_i + 1}, \ldots, s_{r_i}])$, answer to the $i$-th query.

输出 $q$ 行，第 $i$ 行输出一个整数 —— $f([s_{l_i}, s_{l_i + 1}, \ldots, s_{r_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.

第一个示例展示了题面中的一个例子。

$f([7, 3, 1, 7]) = 1$：操作序列为 $[7, 3, 1, 7] \to [(7 + 3)\bmod 10, (1 + 7)\bmod 10]$ $=$ $[0, 8]$，并获得 $1$ 颗糖果（因为 $7 + 3 \ge 10$），接着 $\to$ $[(0 + 8) \bmod 10]$ $=$ $[8]$，因此总共只获得 $1$ 颗糖果。

$f([9]) = 0$，因为我们不对单元素序列执行任何操作。