Opening Ceremony#4305
The director of the Vekua Cup opening ceremony has devised a plan to introduce the teams from various universities: a sequence of individuals will appear on stage. Each university is represented by two participants in this sequence: the first carries a sign displaying the university's name in the language of its country, and the second—ideally a child, as per the director's vision—holds a balloon (in analogy to the ACM ICPC tradition). Thus, the sequence consists of individuals with signs and children with balloons.
The participants have already lined up, but it turns out the sequence is disordered: in some places, two sign carriers are adjacent, and in others, children are grouped together. With so many participants, issuing commands to everyone simultaneously would result in chaos, so the director can only instruct two adjacent people to swap places. Since the order of university representation is not crucial (this is the opening ceremony, not the results announcement), the director's goal is to ensure the sequence starts with a sign carrier and that no two sign carriers or two children with balloons are adjacent anywhere in the sequence. The director seeks to determine the minimum number of swaps required to achieve this arrangement.
The first line of the input contains a natural number n \le 10^6, representing the number of teams. The following lines each contain an integer describing the sequence, starting from its head: if a child with a balloon is at that position, or 0 \le k \le 10^9 (a code representing the language on the sign) if a sign carrier is at that position.
Output a single integer—the minimum number of swaps the director needs to make to achieve the desired alternation.
Example 1