Lexicographically Minimum Sequence via Paired Swaps

You are given a sequence \(A = [a_1, a_2, \dots, a_n]\) of \(n\) integers, where \(a_i\) represents the height of the \(i\)-th succulent. In order to make the arrangement more aesthetic, you are allowed to perform exactly one operation as follows:

• Select an even-length subsequence of indices \(P = [P_1, P_2, \dots, P_{2k}]\) (possibly empty) from \(\{1, 2, \dots, n\}\).
• For every \(i = 1, 2, \dots, k\), swap the values \(A_{P_{2i-1}}\) and \(A_{P_{2i}}\).

After performing the swaps, the succulents are put back in their original positions (with swapped values in the chosen positions). Your task is to determine the lexicographically smallest possible sequence \(A'\) that can be obtained by applying this operation once.

Formal Description

Given a sequence \(A = [a_1, a_2, \dots, a_n]\), you may choose a natural number \(k\) and an even-length (i.e. \(2k\)) subsequence \(P\) of indices from \(\{1,2,\dots,n\}\). For every \(i = 1,2,\dots,k\), you swap \(A_{P_{2i-1}}\) and \(A_{P_{2i}}\). Among all sequences obtained in this way, find the one that is lexicographically smallest.

Lexicographical Order

For two sequences \(A\) and \(B\) of length \(n\), we say \(A\) is lexicographically smaller than \(B\) if there exists an index \(i\) (\(1 \le i \le n\)) such that \(a_1 = b_1, a_2 = b_2, \dots, a_{i-1} = b_{i-1}\) and \(a_i < b_i\).

inputFormat

The first line contains a single integer \(n\) (the number of succulents).

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) representing the heights of the succulents.

Note: The input/output format is special and must be followed exactly.

outputFormat

Output the lexicographically smallest sequence \(A'\) obtainable after performing at most one paired-swap operation. Print the \(n\) integers in one line separated by a single space.

sample

3
3 2 1

1 2 3