Find the next permutation. Assume that permutation (n,n−1,...,2,1) is followed by the identity (1,2,...,n−1,n).
First line contains the number n (1≤n≤105) of elements in the permutation. Second line contains a permutation of n integers.
Print n numbers — the next permutation for the given one.