Maximum Cost Permutation

For any completed permutation $a$, define a position $i$ as bad if $a_i \ne i$.

The key fact is:

• if there are no bad positions, the permutation is already sorted, so the cost is $0$;
• otherwise, if the first bad position is $l$ and the last bad position is $r$, the cost is exactly $r-l+1$.

Why? Any segment we sort must contain every bad position, because positions outside the sorted segment will not change. So the segment must at least cover $[l,r]$.

And sorting $[l,r]$ is enough: everything outside $[l,r]$ is already correct, meaning those outside positions contain exactly their own values. Since the whole array is a permutation, the values left inside $[l,r]$ must be exactly $l,l+1,\dots,r$. Sorting them puts them in the right places. Nice and brutally simple.

So now the problem becomes: maximize the distance between the leftmost and rightmost bad positions after filling zeros.

Forced positions

For a nonzero position $i$:

• if $p_i=i$, it is forced correct;
• if $p_i\ne i$, it is forced bad.

No magic. A fixed wrong value stays wrong.

Now consider zeros.

Let the zero positions be the places we need to fill, and let the missing numbers be the unused values. Their counts are equal.

If there is exactly one zero at position $z$, then there is exactly one missing value $x$:

• if $x=z$, the position becomes correct, forced;
• if $x\ne z$, the position becomes bad, forced.

If there are at least two zeros, then every zero position can be made bad at the same time. If a zero position would naturally receive its own index, just rotate/swap missing values among the zero positions. With at least two items, avoiding fixed points is possible here. Basically, don't hand anyone their own homework back.

Therefore, build the set of positions that can/ must be bad in the maximum construction:

1. Add every fixed position $i$ where $p_i\ne 0$ and $p_i\ne i$.
2. If there are at least two zeros, add all zero positions.
3. If there is exactly one zero at position $z$, add it only if the single missing value is not $z$.

Then the answer is:

• $0$ if this set is empty;
• otherwise $\max(\text{bad})-\min(\text{bad})+1$.

Complexity

Each test case is processed in $O(n)$ time and $O(n)$ memory for marking used numbers. Across all tests, this is $O(\sum n)$, which easily fits.