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
nowshadsub15:
20220412 10:00:30
Solved without stack, used sorting and frequency table of 1 to 9 

manurag_20:
20220222 11:11:46
try greedy : ) 

hellooo:
20220110 10:11:55
I wonder how multiset still passes, although it is O(n log n) 

raghav2130:
20220105 11:26:01
next_permutation has a TC of N*N!


vinoth0708:
20211110 09:40:51
why we use next_permutation just simple approach 

mnnit_1:
20211030 10:48:36
nayan_awati01 for 687 o/p will be 768 not 786


aniket_7781:
20210627 18:29:24
dont miss (1) condition ;( Last edit: 20210627 18:30:33 

utkarsh0124:
20210304 05:42:36
@gnomegeek no need for sorting, it will be an overhead. Can be done in linear time O(n). Stacks will do just fine.


gnomegeek:
20210126 19:50:23
medium difficulty. Need to use sort, stack and logic <3. lovely question. 

satyamkr118:
20201204 06:50:17
My soln is not getting accepted even if i am doing after watching tutorial. 
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 