Strange Operation (Easy Version)

The operation looks index-based, but the real structure is value-based.

If an operation is performed with some $x$, the three involved values are exactly:

• $x$,
• $x+1$,
• $x+2$.

The value $x+2$ must be at the leftmost chosen index. After the operation, that leftmost index gets value $x$.

So the operation is basically: if a value has the two consecutive smaller values somewhere to its right, it may drop by $2$. The two smaller values get pushed upward by $1$.

Do not just greedily apply the first currently valid operation. That can lose. Order matters, and blindly spamming moves is how you get a very confident wrong answer. The correct greedy is about deciding where each final value goes.

Key Question

Suppose we are currently trying to place the smallest not-yet-fixed value, call it $c$.

Which current values $v$ can be turned into $c$?

There are two requirements.

First, parity:

$v$ can only decrease by $2$ each time, so we need $v$ and $c$ to have the same parity.

Second, all smaller needed values must be on the right.

To reduce $v$ to $v-2$, we need values $v-2$ and $v-1$ to the right of $v$.

Then to reduce $v-2$ to $v-4$, we need $v-4$ and $v-3$ to the right.

Continuing this, to reduce $v$ all the way to $c$, every value in $[c, v-1]$ must be to the right of the position containing $v$.

Equivalently:

$value$v$is feasible for$c$iff$pos[v]$is smaller than every$pos[x]$for$c <= x < v$, and$v \equiv c \pmod 2$.$

That means $v$ must be a new leftmost record while scanning values from $c$ upward.

Greedy Choice

We build the answer by placing values $1,2,3,\ldots,n$.

When placing $c$, all values smaller than $c$ are already fixed. Among all feasible values $v$ that can become $c$, we choose the one with the leftmost position.

Why? Because the final permutation is compared left to right. If we can place $c$ at some index, placing it farther right is instantly worse: at the earlier feasible index, the other answer has something larger than $c$. No later cleverness can fix that. Lexicographic order is brutal like that.

How do we find the leftmost feasible value?

Scan $v=c,c+1,\ldots,n$ and keep:

$mn = min(pos[c], pos[c+1], ..., pos[v])$.

Whenever $pos[v]$ becomes a new minimum, value $v$ satisfies the right-side condition. If its parity matches $c$, it is feasible. Since record positions strictly move left, the last feasible record we see is the leftmost feasible position.

There is always at least one feasible choice: $v=c$ itself.

Simulating Many Operations At Once

Suppose we chose position cur, whose current value is $v$, and we want to turn it into $c$.

Actually doing all operations one by one is unnecessary.

The chain does this:

• the chosen position becomes $c$;
• every value in $[c, v-1]$ increases by $1$;
• values greater than $v$ do not change.

Example: reducing $5$ to $1$ uses pairs $(3,4)$ and $(1,2)$. In the end:

$1 \to 2$, $2 \to 3$, $3 \to 4$, $4 \to 5$, and $5 \to 1$.

So it is just a rotation of values $c,c+1,\ldots,v$.

Implementation-wise:

1. Let val = p[cur].
2. Set p[cur] = c.
3. For every old value x in [c, val-1], increment the element at pos[x].
4. Update inverse positions by shifting: pos[val] = old pos[val-1], ..., pos[c+1] = old pos[c], and pos[c] = cur.

Then continue with $c+1$.

Correctness Sketch

A value $v$ can become $c$ only if parity matches and every value $c..v-1$ is to its right. Necessity comes directly from the operation requirements at each decrease step.

Those conditions are also sufficient: reduce $v$ by $2$ repeatedly. At each step, the next two needed smaller values are still to the right, so the operation is valid.

The greedy choice is forced by lexicographic order. At step $c$, all smaller values are already fixed. The first place where the final array can improve is the position where we put $c$. Therefore putting $c$ at the leftmost feasible position is always optimal.

After applying the one-shot rotation, the remaining unfixed values are exactly $c+1,c+2,\ldots,n$, still forming a permutation, so the same argument applies recursively.

Thus the algorithm constructs the lexicographically smallest reachable permutation.

Complexity

For each $c$, we scan up to $n$ values and do up to $n$ update work. So the complexity is $O(n^2)$ per test case, which is exactly what the easy version allows.