Юля выписала на доску n последовательных натуральных чисел a, a+1, …, a+n−1 и написала под каждым из них сумму его цифр в десятичной записи, под i-м числом было выписано sumi.
После этого Юра стёр исходные числа и оставил только их суммы цифр. От вас требуется восстановить первое число в исходной последовательности a.
Входные данные
В первой строке содержится одно целое число n (2 <= n <= 100000) - длина исходной последовательности.
В следующей строке содержатся n целых чисел sum1, sum2, …, sumn (1 <= sumi <= 90) - суммы цифр чисел исходной последовательности.
Гарантируется, что для всех тестов существует подходящее a, такое что 1 <= a <= 1018.
Выходные данные
Выведите одно число
a (1 <=
a <= 10
18) - первое число исходной последовательности. В случае, если существует несколько подходящих
a, можно вывести любое.
Примечание
В первом тестовом примере сумма цифр 1 равняется 1, сумма цифр 2 равняется 2, сумма цифр 3 равняется 3, что соотносится с массивом sum, поэтому a = 1 подходит под условие задачи.
Во втором тестовом примере сумма цифр 77 равняется 14, сумма цифр 78 равняется 15, сумма цифр 79 равняется 16, сумма цифр 80 равняется 8, сумма цифр 81 равняется 9, что соотносится с массивом sum, поэтому a = 77 подходит под условие задачи.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3
1 2 3
|
1
|
| 2 |
5
14 15 16 8 9
|
77
|