Signed Binary Expansion

A binary expansion of an integer $n$ is a sequence of "digits" $a_k a_{k-1} \ldots a_1 a_0$ that satisfies all three of the following conditions:

1. every digit $a_0, a_1, \ldots, a_k$ is equal to $1$, $0$, or $-1$;
2. the most significant digit $a_k$ is not zero;
3. $n = a_k \cdot 2^k + a_{k-1} \cdot 2^{k-1} + \cdots + a_1 \cdot 2 + a_0$.

A single integer can have many different binary expansions. Among all of them, the ones with the fewest nonzero digits are called optimal. For example, writing $-1$ as $\overline{1}$ for convenience, the binary expansions of $15$ include $1000\overline{1}$, $1111$, and $100\overline{1}1$. The first one, $1000\overline{1} = 16 - 1 = 15$, has only $2$ nonzero digits, so it is an optimal expansion of $15$.

Write a program that, given an integer $n$, computes the number of nonzero digits in its optimal binary expansion.

The first line contains an integer $r$ ($1 \le r \le 500$). The second line contains an integer $n$ made up of $r$ decimal digits. The number $n$ is written starting from its most significant digit (that is, in the usual order) and begins with a nonzero digit.

Print, on a single line, the number of nonzero digits in the optimal binary expansion of $n$.