Clearly, if we want to make as few operations as possible, we won’t do any operations where the sets \(S_i\) and \(S_{i+1}\) are equal.

Let’s keep an imaginary permutation \(P\) of numbers from \(1\) to \(N\), which is initially \((1, 2, \ldots, N)\). When we do an operation with sets \(S_i\), \(S_{i+1}\), let’s swap elements \(P_i, P_{i+1}\) of the permutation. Then, we can prove the following statement:

• At any moment, $S_i$ consists of all integers from $min(P[i:N])$ to $max(P[1:i])$, for each $i$.

Clearly, this is true in the beginning. Let’s show that if this statement holds now, it will hold after we make an operation with sets \(S_i, S_{i+1}\).

If \(P_i>P_{i+1}\), then clearly \(max(P[1:i]) = max(P[1:(i+1)])\) and \(min(P[i:N]) = min(P[(i+1):N])\). But then \(S_i\) would be same as \(S_{i+1}\), and it wouldn’t make any sense to do operation with them. So, \(P_i<P_{i+1}\).

Then \(S_i\cup S_{i+1}\) is equal to \([min(P[i:N]), max(P[1:(i+1)])]\), and it’s easy to see that \(min(P[i:N]) = min(P[(i+2):N]\cup \{P[i]\})\) and \(max(P[1:(i+1)]) = max(P[1:(i-1)]\cup \{P_{i+1}\})\), so after the swap all equalities will still hold.

From the process, it’s easy to observe, that the number of operations is precisely equal to the number of inversions in \(P\). It means that we now have to solve the following problem:

• Does there exist a permutation $P$ of numbers from $1$ to $N$, for which $max(P[1:i]) = R_i$ and $min(P[i:N]) = L_i$ for each $i$? If such permutations exist, find the smallest possible number of inversions in them.

Clearly, we must have \(L_i \le L_{i+1}\) and \(R_i \le R_{i+1}\) for each \(i\). Also, when \(L_i \neq L_{i+1}\), we know that \(P_i\) must be equal to \(L_i\), and also \(P_N\) has to be equal to \(L_N\). Similarly, \(P_1 = R_1\) and whenever \(R_i \neq R_{i+1}\), we must have \(P_{i+1} = R_{i+1}\).

This way, we can uniquely determine some elements of \(P\). If we had to assign some element to more than one position, there is no such permutation \(P\).

What about the remaining numbers, which haven’t been assigned yet? It’s easy to see that it’s optimal to put them in remaining positions in increasing order: if there is some their assignment to the remaining positions which doesn’t “ruin” prefix maximums and suffix minimums, then sorted order won’t either. Additionally, it’s easy to see that putting them in the increasing order minimizes the number of inversions! Two rabbits with one shot.

So, the algorithm would be to determine some “definite” positions, put all remaining elements in the increasing order, check if prefix maximums and suffix minimums match, and if they do, output the number of inversions in the given permutation. Total complexity \(O(N\log{N})\).

Bonus: Reduce the complexity to \(O(N)\)