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
piyush490:
20200219 18:40:04
Reversing dosen't work


raipavitra:
20200213 10:41:39
just use next_permutation with some pruning. 

sayal_hajare:
20200209 17:58:17
My idea: scan from right, and the first time you see the next digit smaller than current, swap them and print; if you don't see any, print 1.


runmachine__18:
20200120 20:31:48
just solved it in O(n) 

bhagyasingh012:
20200120 14:22:42
Finally did it!!


princebaweja1:
20200108 18:19:29
@blank97 no


shreyakjain14:
20200105 04:25:43
why am i getting wrong answer? 

blank97:
20191218 18:45:42
does the n digits can contain negative numbers too ?


sd327:
20191202 12:02:41
I am trying to do it in Python3. I am getting runtime error. What to do? 

rock_puneet:
20191031 10:19:32
@owl_a same here 
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 