Define the following functions:

• \(count(l,r,a,b) = \) The number of indices \(i\) such that \(l \le i \le r\) and \((A_i,B_i)=(a,b)\).
• \(reverse(l,r,a,b,c,d) = \) The number of pairs \((i,j)\) such that \(l \le i < j \le r\) and \((A_i,B_i)=(a,b),(A_j,B_j)=(c,d)\).

To simplify the discussion, if necessary, insert \((1,2)\) and \((1,3)\) at the beginning and \((2,3)\) at the end of \((A_i,B_i)\) to ensure the existence of \(i\) that satisfies \((A_i,B_i)=(1,2),(1,3),(2,3)\).

The optimal solution will be such that for \(i\) satisfying \((A_i,B_i)=(1,2)\), \(C_i=1\) if \(i \le x\), and \(C_i=2\) if \(i > x\). (Similarly, for \((1,3)\) and \((2,3)\), there are some \(y\) and \(z\) that form such a pattern.)

For later convenience, we only consider values of \(x\) that can be taken as \(i\) satisfying \((A_i,B_i)=(1,2)\) or \(i-1\) for the smallest \(i\) satisfying \((A_i,B_i)=(1,2)\). This does not lose generality. The same applies to \(y\) and \(z\).

Now, let \(P_x, Q_y, R_z\) denote the numbers of inversions with \(i\) such that \(A_i=B_i\) when \(x, y, z\) are fixed, respectively.

Let’s fix the magnitude relationship between \(x,y,z\). For example, consider the case \(x < y < z\). The number of inversions in this case is the sum of the following values:

• $P_x + Q_y + R_z$
• The number of pairs $(i,j)$ such that $x < i < j \le y$ and $(A_i,B_i)=(1,2),(A_j,B_j)=(1,3)$ ($=reverse(x+1,y,1,2,1,3)$)
• The number of pairs $(i,j)$ such that $y < i < j$ and $(A_i,B_i)=(1,3),(A_j,B_j)=(1,2)$ ($=reverse(y+1,n,1,3,1,2)$)
• The number of pairs $(i,j)$ such that $i < j \le x$ and $(A_i,B_i)=(2,3),(A_j,B_j)=(1,2)$ ($=reverse(1,x,2,3,1,2)$)
• The number of pairs $(i,j)$ such that $z < i < j$ and $(A_i,B_i)=(2,3),(A_j,B_j)=(1,2)$ ($=reverse(z+1,n,2,3,1,2)$)
• The number of pairs $(i,j)$ such that $i < j \le y$ and $(A_i,B_i)=(2,3),(A_j,B_j)=(1,3)$ ($=reverse(1,y,2,3,1,3)$)
• The number of pairs $(i,j)$ such that $y < i < j \le z$ and $(A_i,B_i)=(1,3),(A_j,B_j)=(2,3)$ ($=reverse(y+1,z,1,3,2,3)$)

Upon closer inspection, there are no terms where \(x\) and \(z\) interact. Therefore, it suffices to find the minimum values of the part involving \(x\) and the part involving \(z\) separately when \(y\) is fixed.

Now, let’s consider the value of \(x\) that minimizes its part when \(y\) is fixed. The terms to consider are \(P_x\) and \(reverse(x+1,y,1,2,1,3),reverse(1,x,2,3,1,2)\) from the above. The latter is automatically determined once \(x\) is decided, but the former term depends on both \(x\) and \(y\), which makes it difficult. Here, we decompose \(reverse(x+1,y,1,2,1,3)\) as follows:

\(reverse(x+1,y,1,2,1,3)=reverse(1,y,1,2,1,3)-reverse(1,x,1,2,1,3)-count(1,x,1,2) \times count(x+1,y,1,3)\)

\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =reverse(1,y,1,2,1,3)-reverse(1,x,1,2,1,3)+count(1,x,1,2) \times count(1,x,1,3) - count(1,x,1,2) \times count(1,y,1,3)\)

This decomposition has the form of \(reverse(x+1,y,1,2,1,3) = f(x) + g(y) + p(x)q(y)\). Therefore, we can use the Convex Hull Trick to find the minimum value of the \(x\) part for each \(y\). Similarly, we can process the \(z\) part.

This allows us to handle the case \(x < y < z\), and the cases \(y < z < x\) and \(z < x < y\) can be processed similarly.

The case \(x < z < y\) behaves slightly differently from the above cases. As before, we decompose the number of inversions into several terms.

• $P_x + Q_y + R_z$
• $reverse(1,x,2,3,1,2)$
• $reverse(z+1,n,2,3,1,2)$
• $reverse(1,y,2,3,1,3)$
• $reverse(x+1,y,1,2,1,3)=reverse(1,y,1,2,1,3)-reverse(1,x,1,2,1,3)+count(1,x,1,2)\times count(1,x,1,3) - count(1,x,1,2) \times count(1,y,1,3)$
• $reverse(1,y,1,3,1,2)$

Now, let’s assume \(x\) and \(y\) are fixed. Then, due to the convexness of \(R_z + reverse(z+1,n,2,3,1,2)\), it can be seen that the optimal \(z\) is one of the following: the smallest \(z\) greater than or equal to \(x\), the largest \(z\) less than or equal to \(y\), and the \(z\) that minimizes \(R_z + reverse(z+1,n,2,3,1,2)\) overall. We can process each case quickly using the Convex Hull Trick.

The cases \(y < x < z\) and \(z < y < x\) can also be processed similarly. Thus, we have been able to handle all patterns.

The computational complexity is \(\mathrm{O}(N)\) or \(\mathrm{O}(N\log N)\). (\(\mathrm{O}(N\log^2 N)\) solutions with an extra log factor in divide-and-conquer + CHT for the \(x < z < y\) pattern might need to improve constant factors.)