Stay or Mirror

Let an index be stay if we choose $a_i=p_i$, and mirror if we choose $a_i=2n-p_i$.

For a pair $i<j$, set $x=p_i$ and $y=p_j$. There are only four cases:

| choice at $i$ | choice at $j$ | inversion? | |---|---|---| | stay | stay | yes iff $x>y$ | | stay | mirror | never | | mirror | stay | always | | mirror | mirror | yes iff $x<y$ |

The mixed cases are the important part: every mirrored value is at least as large as every stayed value, and since $p$ is a permutation, the only equality edge case does not create trouble. So mirror/stay always loses, stay/mirror always behaves.

Now deconstruct the pair by asking: where is the smaller value?

Case 1: $p_i>p_j$

The smaller value is at index $j$, on the right.

The pair contributes:

• $1$ if index $j$ chooses stay,
• $0$ if index $j$ chooses mirror.

The choice of index $i$ does not matter for this pair. Weird-looking, but true from the table.

So if a value has a larger value to its left, choosing stay pays $1$ for that larger value.

Case 2: $p_i<p_j$

The smaller value is at index $i$, on the left.

The pair contributes:

• $0$ if index $i$ chooses stay,
• $1$ if index $i$ chooses mirror.

Again, the larger value's choice does not matter.

So if a value has a larger value to its right, choosing mirror pays $1$ for that larger value.

Local cost

For each position $i$, define:

• $L_i =$ number of indices $j<i$ such that $p_j>p_i$.
• $R_i =$ number of indices $j>i$ such that $p_j>p_i$.

If we choose stay at $i$, we pay $L_i$.

If we choose mirror at $i$, we pay $R_i$.

And here is the nice part: these costs are independent for every index. No DP, no graph cut, no cursed bitmask nonsense. Each inversion pair charges exactly one endpoint: the endpoint with the smaller permutation value.

Therefore the minimum possible number of inversions is

$$\sum_{i=1}^{n} \min(L_i, R_i).$$

Since $\sum n\le 5000$, an $O(n^2)$ implementation is completely fine: for each $i$, scan left and right and count larger values.

Complexity

Per test case:

• Time: $O(n^2)$
• Memory: $O(n)$