445. Next Greater Permutation

0

Medium

Given an array of positive integers, find the next lexicographically greater permutation of the array. If such arrangement is not possible, return the array sorted in ascending order. You are given an array A of size N. Find the next greater permutation of array A.

Input Format

The first line contains an integer N, the size of the array. The second line consists of the array A.

Output Format

Print the next permutation of array A.

Example

Input

3
2 1 3

Output

2 3 1

Constraints

1 <= A[i] <= 10^5
1 <= N <= 10^5

Loading...

View Submissions

Console