Flipping Coins

Interview

Time limit1sMemory limit128 MB

Summary

Count the heads and tails and flip the coins on the less frequent side so all coins show the same face.

Level: Easy1 of 10
Topics: Greedy, Array
Solved: No attempts yet

Problem

Bajtek has $n$ coins. Each coin has two sides, heads and tails, and all of them are currently lying on a table. Bajtek wants every coin to show heads, or every coin to show tails. Find the minimum number of coins he has to flip to the other side to achieve this.

Input

The first line contains one integer $n$ ( $1 \le n \le 10^6$ ), the number of coins.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ separated by spaces. Here $a_i$ describes the $i$ -th coin: it is $0$ if the coin shows heads and $1$ if it shows tails.

Output

Print a single integer: the minimum number of coins Bajtek has to flip so that all coins show the same side.

Examples1

Example 1
Input
```
6
1 0 1 1 1 0
```
Expected output
```
2
```