Given an integer n and a permutation of numbers 1, 2 ... , n-1, n write a program to print the permutation that lexicographically precedes the given input permutation. If the given permutation is the lexicographically least permutation, then print the input permutation itself.

Input Format:

First line is the test cases and second line contains value of integer n: 1 <= n <= 1,000,000 third line is a space separated list of integers 1 2 ... n permuted in some random order

Output Format:

Output a single line containing a space separated list of integers which is the lexicographically preceding permutation of the input permutation.