Tie Game in a Boolean Array

Bessie and Elsie play a game on a Boolean array A of length \(2N\) (with \(1 \le N \le 10^5\)). Bessie's score is equal to the number of inversion pairs in the first half of the array and Elsie's score is equal to the number of inversion pairs in the second half. An inversion pair in a segment is defined as a pair of indices \(i<j\) such that \(A[i]=1\) and \(A[j]=0\). For example, if a segment contains a block of \(X\) ones followed by a block of \(Y\) zeros then the inversion count in that segment is \(XY\).

Farmer John has stumbled upon their game and wonders: what is the minimum number of adjacent swaps needed so that the game ends in a tie? In other words, determine the minimum number of adjacent swaps required so that the inversion count computed in the first half equals the inversion count computed in the second half.

Note: You are allowed to swap any two adjacent elements anywhere in the array. Swaps can cross the half‐boundary, thereby altering the number of ones and zeros in each half. In the final configuration the first half (indices \(0\) to \(N-1\)) and the second half (indices \(N\) to \(2N-1\)) must both be arranged in non‐decreasing order (i.e. all \(0\)s then all \(1\)s) so that both inversion counts are \(0\), which is a tie.

The trick is to decide how many ones should be allocated to the first half. Suppose we decide that the final configuration should have \(X\) ones in the first half, and thus \(T-X\) ones in the second half if \(T\) is the total number of ones in the array. Then:

• The first half will have \(N-X\) zeros followed by \(X\) ones. The target positions for the ones in the first half will be indices \(N-X, N-X+1, \ldots, N-1\).
• The second half will have \(N-(T-X)\) zeros followed by \(T-X\) ones. The target positions for the ones in the second half will be indices \(2N-(T-X), \ldots, 2N-1\).

If we record the indices of the ones in the original array as \(P[0 \ldots T-1]\) (in increasing order) and define \(A[i] = P[i] - i\), then it can be shown that the minimum number of adjacent swaps needed to get a set of items into a block of consecutive target positions equals the sum of the absolute differences between the current positions and the target positions. In our setting the total cost can be written as:

[ \text{Cost}(X) = \sum_{i=0}^{X-1} \left|P[i] - (N-X+i)\right| + \sum_{i=X}^{T-1} \left|P[i] - \Bigl(2N - (T-X) + (i-X)\Bigr)\right|. ]

Your task is to try every valid \(X\) (where \(X\) can range from \(\max(0, T-N)\) to \(\min(N, T)\)) and compute the minimal total cost. This minimal cost is the answer — the minimum number of adjacent swaps Farmer John needs to make the game a tie.

inputFormat

The first line contains a single integer \(N\) (half the length of the array). The second line contains \(2N\) space‐separated integers, each of which is either \(0\) or \(1\), representing the array \(A\).

outputFormat

Output a single integer: the minimum number of adjacent swaps required to make the inversion counts of the first and second halves equal (i.e. both equal to \(0\) when arranged in non-decreasing order).

sample

1
1 0

0