A. Number Splitting
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Tyger has an array of positive integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ of length $$$n$$$, on which he wants to perform a series of operations. An operation on an array consists of removing a number $$$x$$$ from the array and adding two positive integers $$$y$$$ and $$$z$$$ to the array such that $$$x = y + z$$$ and the addition doesn't yield any carries. Find the maximum possible number of operations Tyger can perform on the array.

Input

The first line contains a single integer $$$n$$$ $$$(1 \leq n \leq 100)$$$, representing the length of the array.

The following line contains $$$n$$$ positive integers $$$a_1, a_2, \dots ,a_n$$$ $$$(1 \leq a_i \leq 10^{10^4})$$$, representing Tyger's original array.

Output

Output a single integer, the maximum number of operations that can be done on array $$$a$$$.

Scoring
SubtaskConstraintPoints
$$$1$$$$$$a_i \leq 9$$$$$$30$$$
$$$2$$$$$$a_i \leq 10^9$$$$$$40$$$
$$$3$$$No additional constraints$$$30$$$
Example
Input
4
1 2 3 11
Output
4
Note

The first element, $$$1$$$, cannot be split any further using an operation. Tyger can complete an operation and split $$$2$$$ into $$$1$$$ and $$$1$$$, and since $$$1$$$ cannot be split any further, $$$2$$$ allows for one operation. $$$3$$$ can be split into $$$2$$$ and $$$1$$$, and since $$$2$$$ can be split once and $$$1$$$ can be split no more times, we can complete a total of two operations. $$$11$$$ can be split into $$$10$$$ and $$$1$$$, allowing for one operation.

Therefore, Tyger can complete a total of $$$1 + 2 + 1 = 4$$$ operations on this array.