Glass Bead

It looks like a clear glass bead

But it will not break so easily

I love you, so you will not change

I will shine on you forever

You want to build a structure that does not break, using glass beads.

The structure is built by placing glass beads on the points $(x,y)$ of the pyramid grid below. ($x, y$ are integers greater than or equal to $0$)

To keep the structure from breaking at every point with $y>0$, it must satisfy the following condition.

• A glass bead can be at $(x,y)$ only if there are glass beads at both $(x,y-1)$ and $(x+1,y-1)$.

The information for the row $y=0$ of the structure is given. Place glass beads at points with $y>0$ as you see fit. Find the maximum number of glass beads the resulting structure can have.

The first line contains the range $N$.

The second line contains the information for the row $y=0$ of the structure as a string of length $N$. If the $i$-th character is 1, there is a glass bead at $(i-1,0)$. Otherwise, there is no glass bead there. ($1\leq i\leq N$)

There are no glass beads at $(x,0)$ outside the range ($x\geq N$).

Print the maximum number of glass beads in the structure on the first line.

$1\leq N\leq 200000$

The answer can exceed the range of C++ int, so using the long long type is recommended.