### PROBLEM LINK:

**Author:** Alexey Zayakin

**Testers:** Hasan Jaddouh

**Editorialist:** Alexey Zayakin

### DIFFICULTY:

Cakewalk

### PREREQUISITES:

Constructive algorithms, longest increasing subsequence

### PROBLEM:

For an n-digit number x we define the LIS array as follows: i-th element of the array is the length of the longest strictly increasing subsequence of numbers x digits that ends with the i-th digit.

Given the LIS array of some n-digit number, find any x that corresponds to this LIS array.

### QUICK EXPLANATION:

We can interpret the array in the input as array of digits of x, i.e. the i-th digit of x will be equal to the i-th element of the LIS array.

### EXPLANATION:

Let’s denote the i-th digit of number x with d_i, i.e. x = \overline{d_1 d_2 \dots d_n}.

What does it means that LIS* = k? It means that there exists a sequence p_1 < p_2 < \dots < p_{k - 1} < i such that LIS[p_1] = 1, LIS[p_2] = 2, \dots, LIS[p_{k - 1}] = k - 1 and digits d_{p_1}, d_{p_2}, \dots, d_{p_{k - 1}}, d_i form a strictly increasing sequence. The simplest way to make this sequence increasing is to simply assign d_{p_1} = 1, d_{p_2} = 2, \dots, d_{p_{k - 1}} = k - 1, d_i = k or in other words d_j = LIS[j].

Given that n \le 9, it follows that 1 \le LIS* \le 9 and thus all the values of the LIS array are indeed non-zero digits.

### Time Complexity:

\mathcal{O}(n) per test case.

### Bonus:

Can you solve this problem with constraints n \le 100?