题目描述

Yoimiya 有 $n$ 堆火药，有一个长度为 $n$ 的 01 字符串描述这些火药，第 $i$ 堆火药能点燃当且仅当 $a_i=1$．

假设当前还剩 $m$ 堆火药，编号从小到大依次为 $1,2,\cdots,m$，可以选择一堆能点燃的火药 $i$，将其点燃，其会引爆第 $(m-i+1)$ 堆火药并让其消失，但第 $i$ 堆火药不会消失并且在此后依然能被点燃。

注意，虽然火药的编号变了，但是可燃性不会改变。

Yoimiya 想要烟火尽可能地为世人绽放，请求出至多能点燃几次火药。

输入格式

第一行，一个整数 $n$．

第二行，一个长度为 $n$ 的 01 字符串 $a$．

输出格式

一个整数，代表答案。

样例 $1$ 输入

5
00100

样例 $1$ 输出

1

样例 $2$ 输入

5
01010

样例 $2$ 输出

3

样例解释

样例一：只能点燃 $a_3$。

样例二：其中一种最优操作为：

点燃 $a_4=1$，使得 $a_2$ 消失，字符串变为 0010。

之后点燃一次 $a_3=1$，字符串变为 010。

点燃一次 $a_2=1$，字符串变为 00。

一共点燃 $3$ 次。

测试点约束

对于 $100\%$ 的数据，$1\leq n\leq 10^6,a_i\in\{0,1\}$．

各测试点的约束如下表所示，其中 $c$ 表示字符串中有多少字符 1：