Encyclopedia

Time limit1sMemory limit128 MB

Summary

Given a stack of n pages and n sleeves, swap adjacent elements to make the two types alternate, and output the minimum number of swaps.

Level: Medium5 of 10
Topics: Greedy, Array, Prefix sum, Math
Solved: No attempts yet

Problem

Little John loves reading the Bytean encyclopedia, and he is especially fascinated by its colorful illustrations. The encyclopedia is made up of many independent pages. Every so often new pages are printed, and John's parents add them to a binder that already holds all of the earlier pages. To keep the pages from getting dirty, each one is kept inside its own transparent sleeve.

One day John dropped the binder on the floor: every sleeve fell out of the binder, and every page slipped out of its sleeve. Luckily nothing was lost, so the number of loose pages is still equal to the number of loose sleeves. John gathered everything from the floor and piled it into a single stack. Now he wants to put everything back into the binder, but first he has to rearrange the stack so that pages and sleeves alternate. John cannot read, so the order of the pages among themselves does not matter; the only thing that matters is that pages and sleeves end up alternating.

In one move John may swap two adjacent elements of the stack. He stops as soon as pages and sleeves alternate. Compute the minimum number of adjacent swaps needed to reach such an arrangement.

Write a program that:

reads the description of the stack from standard input,
computes the minimum number of adjacent swaps required to make pages and sleeves alternate,
writes the result to standard output.

Input

The first line contains one integer $n$ ( $1 \le n \le 10^6$ ): the number of pages, which is also the number of sleeves in the encyclopedia.

The rest of the input describes the stack as $2n$ non-negative integers. The $i$ -th of these integers describes the $i$ -th element from the top of the stack: it is $0$ if that element is a sleeve, and otherwise it is a positive page number no greater than $10^9$ .

The description contains exactly as many zeros as positive numbers (that is, $n$ of each). Page numbers need not be distinct; the same page number may appear several times.

Output

Print one integer: the minimum number of adjacent swaps needed to rearrange the stack so that pages and sleeves alternate.

Examples4

Example 1
Input
```
5
5
1
0
0
2
4
0
3
0
0
```
Expected output
```
3
```
Example 2
Input
```
1
0
7
```
Expected output
```
0
```
Example 3
Input
```
1
7
0
```
Expected output
```
0
```
Example 4
Input
```
2
0
0
5
5
```
Expected output
```
1
```