Problem C
Howl's Mewing Castle
Howl’s moving castle is currently undergoing renovation, where the walls of the castle are getting sharper and more defined.
The castle has a state that can be described as a single number, which starts off at $0$. The castle can undergo $N$ different processes, which all can be represented as a nonnegative number $a_i$. When using a process $i$, Howl can either add or subtract $a_i$ to the castle’s state number, as long as it stays nonnegative. Howl may choose which processes to use, how to use them, as well as the order in which they are used. Processes can be used at most once.
Naturally, each $1$ in the binary representation of the castle’s state number represents a bump in the wall, which is a flaw. Thus, Howl is trying to minimize the number of flaws, in other words the number of $1$’s in the binary representation of its state.
However, the castle must undergo at least one process as a part of its mandatory monthly maintenance quota. Find the minimum number of flaws the castle can have, subject to these constraints.
Input
The first line contains a single integer $N \: (1 \leq N \leq 10^5)$, denoting the number of different processes. This is followed by $N$ lines, where the $i$th line contains $a_i \: (0 \leq a_i \leq 10^6) $, denoting how much the castle’s state number is modified by process $i$.
Output
Output a single integer, the minimum number of flaws the castle can have, subject to the constraint that the castle must undergo at least one process.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 39 15 30 27 |
2 |
