Minimum Update Operations in a Fenwick Tree

Professor Pang is teaching about the Fenwick tree (or binary indexed tree) which is maintained as an array \(c[1\ldots n]\) initially all zero. In a single update operation, for a given position \(pos\) (with \(1\le pos\le n\)) and a real value \(val\), the following procedure is executed:

def update(pos, val):
    while (pos \(\le n\)):
        c[pos] += val
        pos += pos & (-pos)  \(\quad\text{(here } pos & (-pos) \text{ equals the largest power of }2 \text{ dividing } pos\text{)}\)

After several update operations, professor Pang only remembers for each index \(i\) whether \(c[i]\) is zero or not — that is, a binary string \(b\) of length \(n\) where \(b[i] = 1\) indicates that \(c[i]\) is nonzero, and \(b[i] = 0\) indicates that \(c[i] = 0\). Assuming his memory is accurate, determine the minimum number of update operations that could have produced this pattern.

Note: The update procedure is defined in LaTeX as follows:

[ \texttt{def update(pos, val):} \ \quad \texttt{while } pos \leq n:\ \quad\quad c[pos] \mathrel{+}= val \ \quad\quad pos \mathrel{+}= pos \mathrel{&} (- pos) ]

You are allowed to choose any real value (nonzero when needed) for each update. An update at position \(p\) adds the real \(val\) to every element \(c[i]\) for \(i \in S(p)\) where the set \(S(p)\) is defined by the iterative process in the procedure.

Your task is to compute the minimum number of update operations so that the final \(c\) array satisfies:

• \(c[i] = 0\) if the \(i\)th character of the input pattern is \(0\).
• \(c[i] \neq 0\) if the \(i\)th character of the input pattern is \(1\).

Hint: Since update operations only affect indices \(\ge\) the starting position, a greedy strategy processing indices from 1 to \(n\) can be designed. Whenever the current value \(c[i]\) does not match the target (0 or nonzero), perform an update starting at \(i\) with an appropriate real value to fix it. Along with fixing \(c[i]\) the same update will affect later indices, so care must be taken in order not to disturb previously fixed positions.

inputFormat

The input consists of two lines:

1. The first line contains an integer \(n\) (\(1 \le n \le 10^5\)), the size of the array.
2. The second line contains a binary string of length \(n\). The \(i\)th character is 0 if \(c[i]=0\) and 1 if \(c[i]\) is nonzero.

outputFormat

Output a single integer: the minimum number of update operations that could result in the given memory pattern of the \(c\) array.

sample

3
110

1