Юля выписала на доску $$$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$$$ баллов.