题目描述

给定一个长度为 $n(1 \le n \le 300)$ 的数列 $b_1, b_2, \ldots, b_n(1 \le b_i \le 300)$。

你需要构造出一个长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n$，同时满足如下条件：

• 数列元素均为正整数且严格单调递增，即：$1 \le a_1 \lt a_2 \lt \ldots \lt a_{n-1} \lt a_n$
• 对于任意下标 $1 \le i \le n$，$b_i$ 表示的是 $a_i$ 的数位和（即：$a_i$ 的十进制表示中每一位上的数字之和等于 $b_i$）
• $a_n$ 尽可能地小。

输出 $a_n$ 的最小值。

输入格式

第一行，一个整数 $n(1 \le n \le 300)$。

第二行，$n$ 个整数 $b_1, b_2, \ldots, b_n(1 \le b_i \le 300)$。

输出格式

输出一个整数，表示所有满足如上条件的数列中 $a_n$ 可能的最小值。

样例

3
1 2 3

3

3
3 2 1

100

4
5 10 20 1

1000

说明/提示

样例解释

• 样例1：一个满足条件的数列 $1, 2, 3$
• 样例2：一个满足条件的数列 $3, 11, 100$
• 样例3：一个满足条件的数列 $5, 19, 299, 1000$

说明/提示

• 对于 $30\%$ 的数据，$n, b_i \le 30$
• 对于 $100\%$ 的数据，$1 \le n, b_i \le 300$