JNEXT  Just Next !!!
DevG likes too much fun to do with numbers. Once his friend Arya came and gave him a challenge, he gave DevG an array of digits which is forming a number currently (will be called as given number). DevG was challanged to find the just next greater number which can be formed using digits of given number. Now DevG needs your help to find that just next greater number and win the challenge.
Input
The first line have t number of test cases (1 <= t <= 100). In next 2*t lines for each test case first there is number n (1 <= n <= 1000000) which denotes the number of digits in given number and next line contains n digits of given number separated by space.
Output
Print the just next greater number if possible else print 1 in one line for each test case.
Note : There will be no test case which contains zero in starting digits of any given number.
Example
Input: 2 5 1 5 4 8 3 10 1 4 7 4 5 8 4 1 2 6 Output: 15834 1474584162
hide comments
vivek_01:
20190320 19:52:22
Quite easy ,


aditya_305:
20190130 14:02:19
Done using next_permution function in c++ STL.. LOL


dex_coder007:
20181206 12:44:59
How to do it with stacks? 

ilovemetoo:
20181117 09:24:47
AC in one go!! Yay! 

debsourav33:
20181031 14:09:43
Alright! Done using sorting! Previous O(NlogN) solution using multiset gave TLE but stl sort works! Guess STL sort has slightly better than NlogN runtime.. 

debsourav33:
20181030 15:10:43
10^6 is too big dataset for my beautiful nlogn solution using multiset and binarysearch.. :( 

thesyncoder:
20181024 11:15:22
Little hard,


k_chaitanya98:
20181009 17:40:09
I am running this code in another IDE and getting this correct in JAVA but getting Wrong Answer here .Can Somebody tell me corner cases that I need to cover 

saketag007:
20180930 17:39:57
Easy AC in one go. Check for this test case


shubham_04_04:
20180921 20:26:21
Took 20 attempt to get it correct :( for 25th Last edit: 20180925 17:41:47 
Added by:  ! include(L.ppt) 
Date:  20120831 
Time limit:  1.297s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  MNNIT OPC 31082012 