Transform a permutation so the first positions become the lexicographically smallest possible sequence after at most one swap per position.
Anton and Permutation
You are given a permutation of integers from $1n$. You may perform a sequence of swaps, but each position can be involved in at most one swap.
Your task is to make the permutation as small as possible in lexicographic order under this constraint.
A lexicographically smaller permutation is one that differs at the first position where the two permutations are different, and has the smaller value there.
Idea of the task
Process the permutation from left to right and use swaps only when they improve the prefix as much as possible, while respecting the limit that every index can be used at most once.
This is a classic greedy permutation-rearrangement problem.
Input Format
- The first line contains an integer .
- The second line contains distinct integers describing a permutation of $1..n$.
Output Format
- Print the lexicographically smallest permutation you can obtain under the stated swapping rule.
Constraints
- The array is a permutation of $1..n$
- Each position may participate in at most one swap
Example 1
Input
5 5 4 3 2 1
Output
1 2 3 4 5
Explanation
Swapping elements greedily from the left lets the smallest values move to the front while using each position at most once.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.