P5426 [USACO19OPEN] Balancing Inversions G

Bessie and Elsie are playing a game on a boolean array $A$ of length $2N$ ($1 \leq N \leq 10^5$). Bessie's score is the number of inversions in the first half of $A$, and Elsie's score is the number of inversions in the second half of $A$. An inversion is a pair of elements satisfying $A[i] = 1$ and $A[j] = 0$, where $i < j$. For example, an array with a block of $0$'s followed by a block of $1$'s has no inversions, while an array with $X$ $1$'s followed by $Y$ $0$'s has $XY$ inversions. Farmer John happens to see this board, and he wonders what the minimum number of adjacent swaps is to make the game appear tied. Please help Farmer John compute the answer.

The first line contains $N$. The second line contains $2N$ integers, each being $0$ or $1$.

Output the minimum number of moves needed to make the game tied.

In this example, initially the first half has $1$ inversion and the second half has $3$ inversions. After swapping the $5$-th and the $6$-th numbers, both subarrays have $0$ inversions. Translated by ChatGPT 5