Yulia wrote on the board n consecutive natural numbers a, a+1, …, a +n−1 and wrote under each of them the sum of its digits in decimal notation, under ith number was written sumi.
After that, Yura erased the original numbers and left only their sums of digits. You are required to restore the first number in the original sequence a.
Input
The first line contains a single integer n (2 <= n <= 100000) - the length of the original sequence.
The next line contains n integers sum1, sum2 , …, sumn (1 <= sumi <= 90) - the sum of the digits of the numbers in the original sequence.
It is guaranteed that for all tests there is a suitable a such that 1 <= a <= 1018 .
Imprint
Print a single number
a (1 <=
a <= 10
18) - the first number of the original sequence. In case there are several matching
a, any one can be output.
Note
In the first test case, the sum of 1 digits is 1, the sum of 2 digits is 2, the sum of 3 digits is 3, which corresponds to the sum array, so < tt>a = 1 matches the condition of the problem.
In the second test case, the sum of 77 digits is 14, the sum of 78 digits is 15, the sum of 79 digits is 16, the sum of 80 digits is 8, the sum of 81 digits is bsp; 9, which corresponds to the array sum, so a = 77 fits the condition of the problem.
Examples
| # |
Input |
Output |
| 1 |
3
1 2 3
|
1
|
| 2 |
5
14 15 16 8 9
|
77
|