Smallest Lexicographical Order with One Swap

Given an array of integers, you are allowed to perform at most one swap operation to produce the smallest lexicographical order possible.

Formally, for an array (A) of (n) elements, you want to find an array (B) that is lexicographically minimal among all arrays that can be obtained from (A) by swapping at most one pair of elements.

Recall that an array (X) is lexicographically smaller than an array (Y) if there exists an index (i) such that (X_j = Y_j) for all (j < i) and (X_i < Y_i). For example, if (A = [3, 2, 1, 4, 5]), a single swap between the first and third elements will yield ([1, 2, 3, 4, 5]), which is the answer.

inputFormat

The input consists of two lines. The first line contains an integer (n) ((1 \leq n \leq 10^5)), representing the number of elements. The second line contains (n) space-separated integers.

outputFormat

Output the lexicographically smallest array possible after performing at most one swap. The array should be printed as (n) space-separated integers on one line.## sample

5
3 2 1 4 5

1 2 3 4 5