Zeke and his Password Encryption

All submissions for this problem are available.
Problem statement : 
UVCEian Zeke has been appointed by a bank and the bank manager has asked him to do a really interesting task. The bank manager is facing security problems and feels his company is in a threat of being bankrupt. Hence, he has asked Zeke to help him out and has given him a task to design a way to encrypt passwords.
The bank manager has given Zeke a list of numbers in descending order which are equally spaced.
Zeke needs to design a way to rearrange these numbers and also merge them in such a way that it becomes impossible for hackers to decrypt the passwords.
Since, Zeke feels this can be done in many ways and is confused, the bank manager gives him a list of
information that would be useful for him to encrypt the passwords. So the information provided by his manager is that these numbers are to be arranged in such a way that they should be well balanced depending on the two conditions.
First condition is, for each element, elements to the left are smaller than a particular element and hence become its predecessor and elements to the right are greater than the same element say main element and become its successor.
Also, the second condition is, the difference between the maximum depth of predecessor and that of the successor may be at most one. The manager has told him these two conditions must be followed strictly to encrypt passwords.
Next, to make these passwords more secure he has asked Zeke to put these sequence of numbers after they are balanced in a particular order, where the main element appears first and then the predecessor followed by the successor.
Zeke puts the numbers in to his design (which follow above rules) in the order they appear, if there is a conflict then Zeke rearranges the numbers in his design to satisfy the above rules.
Zeke finds this information useful and also requires your help to design the algorithm.
So you are required to send Zeke the list of encrypted passwords as required by his manager.
NOTE : 
Only one password can be generated from the list of numbers given and also these passwords depending on the size of the list can be of varying length.
Input
Input description.
 The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
 The first line of each test case contains an integer N1 denoting the number of numbers in the list and second line contains N2 denoting a list of numbers
Output
Output description.
 For each test case, output a single line containing the encrypted password.
Constraints
 1 ≤ T ≤ 100
 1 ≤ N1 ≤ 30
 1 ≤ N2 ≤ 10^{2}
Example
Input: 5 3 3 2 1 4 4 3 2 1 5 5 4 3 2 1 6 8 7 6 5 4 2 7 9 7 6 4 3 2 1 Output: 213 3214 42135 542768 4213769
Explanation
Example case 1.
Number of elements are 3.
3 2 1 are arranged in such a way that 1 is to the left of 2 and becomes its predecessor. Also, 3 is to the right of 2 and becomes its successor. So, 2 is displayed first then 1 followed by 3. Hence, we get 213 as the encrypted password.
Author:  hkbharath 
Tags  hkbharath 
Date Added:  21082014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, 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, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 