USACO 2019 US Open Contest, Gold Problem 3. Balancing Inversions

Bessie and Elsie were playing a game on a boolean array AA of length 2N2N (1≤N≤1051≤N≤105). Bessie's score was the number of inversions in the first half of AA, and Elsie's score was the number of inversions in the second half of AA. An inversion is a pair of entries A[i]=1A[i]=1 and A[j]=0A[j]=0 where i<ji<j. For example, an array consisting of a block of 0s followed by a block of 1s has no inversions, and an array consisting of a block of XX 1s follows by a block of YY 0s has XYXY inversions.
Farmer John has stumbled upon the game board and is curious to know the minimum number of swaps between adjacent elements needed so that the game looks like it was a tie. Please help out Farmer John figure out the answer to this question.

INPUT FORMAT (file balance.in):

The first line of input contains NN, and the next line contains 2N2N integers that are either zero or one.

OUTPUT FORMAT (file balance.out):

Please write the number of adjacent swaps needed to make the game tied.

SAMPLE INPUT:
5
0 0 0 1 0 1 0 0 0 1

SAMPLE OUTPUT:
1

In this example, the first half of the array initially has 11 inversion, and the second half has 33 inversions. After swapping the 55th and 66th bits with each other, both subarrays have 00 inversions.
Problem credits: Dhruv Rohatgi

中文版

Bessie和Elsie在一个长为2N2N的布尔数组AA上玩游戏（1≤N≤1051≤N≤105）。Bessie的分数为AA的前一半的逆序对数量，Elsie的分数为AA的后一半的逆序对数量。逆序对指的是满足A[i]=1A[i]=1以及A[j]=0A[j]=0的一对元素，其中i<ji<j。例如，一段0之后接着一段1的数组没有逆序对，一段XX个1之后接着一段YY个0的数组有XYXY个逆序对。
Farmer John偶然看见了这一棋盘，他好奇于可以使得游戏看起来成为平局所需要交换相邻元素的最小次数。请帮助Farmer John求出这个问题的答案。

输入格式（文件名：balance.in）：

输入的第一行包含NN，第二行包含2N2N个为0或1的整数。

输出格式（文件名：balance.out）：

输出使得游戏成为平局最少需要的移动次数。

输入样例：
5
0 0 0 1 0 1 0 0 0 1

输出样例：
1

在这个例子中，初始时前一半有11个逆序对，后一半有33个逆序对。交换了第55和第66个数之后，两个子数组均有00个逆序对。
供题：Dhruv Rohatgi