C. Конфеты!
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим последовательность цифр длины $$$2^k$$$ $$$[a_1, a_2, \ldots, a_{2^k}]$$$. Будем выполнять с ней следующую операцию: заменить пару $$$(a_{2i+1}, a_{2i+2})$$$ на $$$(a_{2i+1} + a_{2i+2})\bmod 10$$$ для $$$0\le i<2^{k-1}$$$. За каждое $$$i$$$ такое, что $$$a_{2i+1} + a_{2i+2}\ge 10$$$, мы получаем конфету! В результате, мы получим последовательность цифр длины $$$2^{k-1}$$$.

Менее формально, последовательность длины $$$2^k$$$ мы разбиваем на $$$2^{k-1}$$$ пар, каждая из которых состоит из двух чисел: первая пара состоит из первых двух чисел, вторая из третьего и четвертого, $$$\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$$$. Вы должны ответить на $$$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$$$.

Входные данные

Первая строка содержит одно целое число $$$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$$$-й запрос.

Примеры
Входные данные
8
8 7 3 1 7 0 9 4
3
1 8
2 5
7 7
Выходные данные
3
1
0
Входные данные
6
0 1 2 3 3 5
3
1 2
1 4
3 6
Выходные данные
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$$$, так как мы не выполняем с ним операции.