Simons and Making It Beautiful

The key is that the condition compares an index to a prefix maximum value:

An index $i$ is ugly iff

$$i = \max(q_1,q_2,\ldots,q_i).$$

This is not asking whether $q_i=i$. That false assumption is the tiny trap here. Do not overcook this into checking all swaps; that is a very Codeforces way to waste five minutes and learn nothing.

First, there is an unavoidable lower bound. At index $n$, the prefix is the entire permutation, so

$$\max(q_1,q_2,\ldots,q_n)=n.$$

Therefore index $n$ is always ugly. No permutation can have fewer than $1$ ugly index.

Now we show this lower bound is achievable. Put the largest value $n$ at the first position. Then for every prefix, the maximum is already $n$:

$$\max(q_1,q_2,\ldots,q_i)=n \quad \text{for all } 1\le i\le n.$$

For every $i<n$, we have $i\ne n$, so those indices are not ugly. For $i=n$, we get $n=n$, so exactly one index is ugly.

Because $p$ is a permutation, the value $n$ appears exactly once. If it is at position $pos$, swap $p_1$ and $p_{pos}$. This uses one operation if $pos\ne 1$, and zero operations if $pos=1$. Both are allowed because the statement says at most once.

So the answer is simply the original permutation after moving $n$ to the front.

Proof of optimality:

• Any output permutation must have index $n$ ugly, so the answer is at least $1$.
• The construction with $q_1=n$ has exactly one ugly index, namely $n$.
• Therefore the construction is optimal.

Edge cases:

• If $n=1$, the only permutation is $[1]$, and it already has exactly one ugly index.
• If $n$ is already first, do not swap anything.
• Otherwise, swap position $1$ with the position containing $n$.

Complexity is $O(n)$ per test case to read the array and find $n$, with $O(1)$ extra space besides the array.

Research checked against the official Codeforces editorial and problem page: https://codeforces.com/blog/entry/151310 and https://codeforces.com/contest/2205/problem/A. A third-party writeup with the same construction appears here: https://www.cnblogs.com/shojig/articles/19644510.