Permutation Flip

Let $F$ be the number of fixed points in the initial permutation.

Suppose we reverse the segment $[l,r]$ and set $s=l+r$. The value originally at position $j$ inside the segment moves to position $s-j$. Hence it becomes a fixed point after the reversal if and only if $A_j=s-j$, or equivalently $j+A_j=s$.

Thus the number of fixed points after reversing $[l,r]$ is

$$F-\#\{j:l \leq j \leq r,\ A_j=j\}+\#\{j:l \leq j \leq r,\ j+A_j=l+r\}.$$

We need to maximize the difference between the subtracted term and the added term.

For a fixed value $s=l+r$, the possible range of $l$ is

$$\max(1,s-N) \leq l \leq \left\lfloor\frac{s-1}{2}\right\rfloor.$$

For a position $j$ satisfying $j+A_j=s$, the condition that $j$ lies inside $[l,$ is equivalent to . For every , store all values with and sort them. Then the number of newly created fixed points for a given can be found by binary search.

The number of old fixed points in a segment is obtained with a prefix sum. For a fixed $s$, as $l$ increases, the number of newly created fixed points changes only after passing one of the stored values, while the number of old fixed points can only decrease. Therefore it is enough to test the smallest possible $l$, and values of the form $x+1$ for stored values $x$.

Each position belongs to exactly one group $s=i+A_i$, so the total number of tested candidates is $O(N)$. The total time complexity is $O(N\log N)$ including sorting and binary searches, and the memory complexity is .

Solution written by GPT5.5