Antiamuny Wants to Learn Swap

For any array $b$, sorting with only adjacent swaps costs exactly the number of inversions. Call this number $I$.

So $g(b)=I$. The only question is whether the one allowed distance-$2$ swap can make the total cost strictly smaller than $I$.

What operation 2 can actually save

Suppose the current three consecutive elements are

$[x,y,z].$

Operation 2 changes this into

$[z,y,x].$

Only the relative order of these three elements changes. Since all values are distinct, there are only a few cases:

• if $x>y>z$, the triple has $3$ internal inversions before and $0$ after, so operation 2 removes $3$ inversions;
• in some cases it removes only $1$ inversion;
• otherwise it makes things worse.

An adjacent swap that helps removes exactly $1$ inversion and costs $1$ operation. So if operation 2 removes only $1$ inversion, congrats, you did nothing special. Same cost, same progress. Very mid.

To get $f(b)<g(b)$, operation 2 must remove $3$ inversions in one operation. Therefore, right before using it, the current array must contain three consecutive elements in strictly decreasing order.

Also, every adjacent swap used before that must be a helpful swap. If you ever swap an already-correct adjacent pair, you add an inversion, and the one special move cannot make the whole route cheaper than $I$.

So the useful scenario is exactly:

1. use only inversion-reducing adjacent swaps;
2. create a consecutive decreasing triple;
3. apply operation 2 and save $2$ operations overall.

The key characterization

A subarray is not perfect iff it contains a decreasing subsequence of length $3$.

That means there exist indices

$i<j<k$

such that

$b_i>b_j>b_k.$

Why?

If such a triple exists, we can use adjacent swaps that only reduce inversions to bring these three values together as a consecutive decreasing triple. Elements bigger than $b_i$ can be pushed to the right, elements smaller than $b_k$ can be pushed to the left, and extra elements between their values can be crossed by $b_i$ until only one middle value remains. Every one of those swaps is an inverted adjacent pair, so no wasted moves.

Then operation 2 changes

$[b_i,b_j,b_k] \to [b_k,b_j,b_i],$

removing $3$ inversions for the price of $1$ operation. After that, finish sorting with normal adjacent swaps. Total cost becomes $I-2$, so the subarray is definitely not perfect.

For the other direction, suppose the subarray is not perfect. Then operation 2 must have removed $3$ inversions, so it was applied to a consecutive decreasing triple $x>y>z$. Since all previous adjacent swaps must have only removed inversions, they never create a new inverted pair; they only delete existing ones. Therefore $x,y,z$ were already pairwise inverted in the original subarray, meaning they formed a decreasing subsequence of length $3$.

So the whole problem becomes:

For each query $[l,r]$, does $a[l\ldots r]$ contain a $321$ pattern?

Turning triples into intervals

For every index $j$, treat it as the middle of the decreasing triple. We need:

• some index $i<j$ with $a_i>a_j$;
• some index $k>j$ with $a_k<a_j$.

Define:

• $L_j$ = nearest previous index with value greater than $a_j$;
• $R_j$ = nearest next index with value smaller than $a_j$.

If both exist, then

$a_{L_j}>a_j>a_{R_j},$

so $[L_j,R_j]$ contains a decreasing triple.

Even better: this nearest choice is enough for all queries. If a query contains any decreasing triple centered at $j$, then its left endpoint is at most some valid previous greater index, so it is also at most $L_j$ because $L_j$ is the nearest one. Similarly, its right endpoint is at least $R_j$ because $R_j$ is the nearest next smaller.

So query $[l,r]$ is bad iff there exists some $j$ such that

$l\le L_j \quad\text{and}\quad R_j\le r.$

Answering queries fast

For every valid interval $[L_j,R_j]$, store:

$best[R_j] = \max(best[R_j], L_j).$

Then prefix-max it:

$best[x] = \max(best[1], best[2], \ldots, best[x]).$

Now $best[r]$ is the largest left endpoint among all bad intervals ending at or before $r$.

For query $[l,r]$:

• if $best[r]\ge l$, some bad interval is fully inside $[l,r]$, so answer NO;
• otherwise answer YES.

We compute $L_j$ and $R_j$ with monotonic stacks:

• previous greater: scan left to right, popping smaller values;
• next smaller: scan right to left, popping larger values.

Total complexity per test case is

$O(n+q),$

which is exactly what we want when the input size is big enough to bully lazy solutions.