유리구슬

투명한 유리구슬처럼 보이지만

그렇게 쉽게 깨지진 않을 거야

사랑해 너만을 변하지 않도록

영원히 널 비춰줄게

유리구슬로 깨지지 않는 구조물을 만들려고 한다.

구조물은 아래 그림과 같은 피라미드 격자의 $(x,y)$ 위치에 유리구슬을 놓아 만든다. ($x, y$는 $0$ 이상의 정수)

$y>0$인 위치의 구조물이 깨지지 않도록, 구조물은 다음 조건을 만족해야 한다.

• $(x,y)$에 유리구슬이 있으려면 $(x,y-1)$과 $(x+1,y-1)$에 모두 유리구슬이 있어야 한다.

구조물의 $y=0$ 부분 정보가 주어진다. $y>0$인 곳에 유리구슬을 적절히 놓아 만들 수 있는 구조물의 유리구슬 개수의 최댓값을 구하라.

첫째 줄에 범위 $N$이 주어진다.

둘째 줄에 구조물의 $y=0$인 곳의 정보가 길이 $N$의 문자열로 주어진다. 문자열의 $i$번째 문자가 1이면 $(i-1,0)$에 유리구슬이 있고, 아니면 유리구슬이 없다. ($1\leq i\leq N$)

범위를 벗어나는 $(x,0)$ ($x\geq N$)에는 유리구슬이 없다.

첫째 줄에 구조물의 유리구슬 개수의 최댓값을 출력한다.

$1\leq N\leq 200000$

답이 C++의 int 범위를 넘을 수 있으므로 long long 자료형을 쓰는 것을 추천한다.