Balancing Inversions#10324
Bessie and Elsie were playing a game on a boolean array of length . Bessie's score was the number of inversions in the first half of , and Elsie's score was the number of inversions in the second half of . An inversion is a pair of entries A_i = and A_j = where < . For example, an array consisting of a block of -s followed by a block of -s has no inversions, and an array consisting of a block of -s followed by a block of -s has 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.
The first line contains ( ≤ ≤ 10^5), and the next line contains integers that are either zero or one.
Write the number of adjacent swaps needed to make the game tied.
In this example, the first half of the array initially has inversion, and the second half has inversions. After swapping the -th and -th bits with each other, both subarrays have inversions.
Example 1