One-Swap Lexicographical Order

Given an array of integers of size \( n \), your task is to perform at most one swap between any two elements in order to obtain the lexicographically smallest sequence possible.

The lexicographical order is defined as follows: Given two sequences \( A = [a_0, a_1, \dots, a_{n-1}] \) and \( B = [b_0, b_1, \dots, b_{n-1}] \), \( A \) is considered lexicographically smaller than \( B \) if there exists an index \( i \) (with \( 0 \le i < n \)) such that for all \( j < i \), \( a_j = b_j \) and \( a_i < b_i \).

You are required to read the input from stdin and output the resulting array to stdout.

inputFormat

The input is given in two lines:

1. The first line contains an integer \( n \) (\( 1 \le n \le 10^5 \)), indicating the number of elements in the array.
2. The second line contains \( n \) space-separated integers.

outputFormat

Output the array after performing at most one swap such that its lexicographical order is minimized. The numbers should be printed in a single line separated by a space.

3
1 2 3

1 2 3