Массив сумм
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Юля выписала на доску $$$n$$$ последовательных натуральных чисел $$$a, a + 1, \ldots, a + n - 1$$$ и написала под каждым из них сумму его цифр в десятичной записи, под $$$i$$$-м числом было выписано $$$sum_i$$$.

После этого Юра стёр исходные числа и оставил только их суммы цифр. От вас требуется восстановить первое число в исходной последовательности $$$a$$$.

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

В первой строке содержится одно целое число $$$n$$$ ($$$2 \le n \le 100\,000$$$) — длина исходной последовательности.

В следующей строке содержатся $$$n$$$ целых чисел $$$sum_1, sum_2, \ldots, sum_{n}$$$ ($$$1 \le sum_i \le 90$$$) — суммы цифр чисел исходной последовательности.

Гарантируется, что для всех тестов существует подходящее $$$a$$$, такое что $$$1 \le a \le 10^{18}$$$.

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

Выведите одно число $$$a$$$ ($$$1 \le a \le 10^{18}$$$) — первое число исходной последовательности. В случае, если существует несколько подходящих $$$a$$$, можно вывести любое.

Примеры

Входные данные
3
1 2 3
Выходные данные
1
Входные данные
5
14 15 16 8 9
Выходные данные
77

Примечание

В первом тестовом примере сумма цифр $$$1$$$ равняется $$$1$$$, сумма цифр $$$2$$$ равняется $$$2$$$, сумма цифр $$$3$$$ равняется $$$3$$$, что соотносится с массивом $$$sum$$$, поэтому $$$a = 1$$$ подходит под условие задачи.

Во втором тестовом примере сумма цифр $$$77$$$ равняется $$$14$$$, сумма цифр $$$78$$$ равняется $$$15$$$, сумма цифр $$$79$$$ равняется $$$16$$$, сумма цифр $$$80$$$ равняется $$$8$$$, сумма цифр $$$81$$$ равняется $$$9$$$, что соотносится с массивом $$$sum$$$, поэтому $$$a = 77$$$ подходит под условие задачи.

Система оценки

В данной задаче $$$25$$$ тестов, помимо тестов из условия, каждый из них оценивается в $$$4$$$ балла. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.

Решения, корректно работающие при $$$1\leq n \leq 2$$$, наберут не менее $$$20$$$ баллов.

Решения, корректно работающие при $$$1\leq n \leq 100$$$, наберут не менее $$$40$$$ баллов.

Решения, корректно работающие при $$$1\leq n \leq 1000$$$, наберут не менее $$$64$$$ баллов.

Решения, корректно работающие при $$$1\leq n \leq 10\,000$$$, наберут не менее $$$80$$$ баллов.