Digit Longest Increasing Subsequences 2

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Recently Chef learned about Longest Increasing Subsequence. To be precise, he means longest strictly increasing subsequence, when he talks of longest increasing subsequence. To check his understanding, he took his favorite ndigit number and for each of its n digits, he computed the length of the longest increasing subsequence of digits ending with that digit. Then he stored these lengths in an array named LIS.
For example, let us say that Chef's favourite 4digit number is 1531, then the LIS array would be [1, 2, 2, 1]. The length of longest increasing subsequence ending at first digit is 1 (the digit 1 itself) and at the second digit is 2 ([1, 5]), at third digit is also 2 ([1, 3]), and at the 4th digit is 1 (the digit 1 itself).
Now Chef wants to give you a challenge. He has a valid LIS array with him, and wants you to find any ndigit number having exactly the same LIS array? You are guaranteed that Chef's LIS array is valid, i.e. there exists at least one ndigit number corresponding to the given LIS array.
Input
The first line of the input contains an integer T denoting the number of test cases.
For each test case, the first line contains an integer n denoting the number of digits in Chef's favourite number.
The second line will contain n space separated integers denoting LIS array, i.e. LIS_{1}, LIS_{2}, ..., LIS_{n}.
Output
For each test case, output a single ndigit number (without leading zeroes) having exactly the given LIS array. If there are multiple ndigit numbers satisfying this requirement, any of them will be accepted.
Constraints
 1 ≤ T ≤ 30 000
 1 ≤ n ≤ 9
 It is guaranteed that at least one ndigit number having the given LIS array exists
Example
Input: 5 1 1 2 1 2 2 1 1 4 1 2 2 1 7 1 2 2 1 3 2 4 Output: 7 36 54 1531 1730418
Explanation
Example case 1. All onedigit numbers have the same LIS array, so any answer from 0 to 9 will be accepted.
Example cases 2 & 3. For a two digit number we always have LIS_{1} = 1, but the value of LIS_{2} depends on whether the first digit is strictly less than the second one. If this is the case (like for number 36), LIS_{2} = 2, otherwise (like for numbers 54 or 77) the values of LIS_{2} is 1.
Example case 4. This has already been explained in the problem statement.
Example case 5. 7digit number 1730418 has LIS array [1, 2, 2, 1, 3, 2, 4]:
index  LIS  length 
1  1730418  1 
2  1730418  2 
3  1730418  2 
4  1730418  1 
5  1730418  3 
6  1730418  2 
7  1730418  4 
Author:  alex_2oo8 
Tester:  kingofnumbers 
Editorial  https://discuss.codechef.com/problems/LISDIGIT 
Tags  alex_2oo8, cakewalk, constructive, cook78, lis 
Date Added:  21012017 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions