Pizza

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

For the banquet on the occasion of the World Programming Semi-final, the organizers bought a pizza divided into \(n\) equal slices (as shown in the figure). Some slices have an olive on them, while others do not.

You already know how the contestants are picky about juice, but they are even more picky about pizza. Not all contestants like olives, so the banquet organizers want to divide the pizza in half in such a way that one of the halves has no olives at all. And to make this possible, they can remove olives from some pizza slices.

However, according to the rules of etiquette, picking olives out of pizza is not very polite, so the organizers ask you to help them calculate the minimum number of olives that need to be removed so that they can divide the pizza into two equal parts such that one of them is completely without olives.

Input

The first line contains an integer \(n\) — the number of pizza slices.

The next line contains \(n\) numbers \(a_i\). \(a_i = 1\) if there is an olive on the \(i\)-th slice of pizza, and 0 otherwise.

Output

In a single line, print an integer — the minimum number of olives that need to be removed.

Constraints

\(1 \le n \le 10^5\),

\(n\) is even,

\(0 \le a_i \le 1\).

Samples

Input (stdin) сopy	Output (stdout) сopy
8 1 0 1 1 0 1 1 1	2

Notes

Pizza from the example with the optimal cut