1323: 魔法卡题少女

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：174 解决：52

题目描述

“与我签订契约，成为魔法少女吧！”。QB这个无耻老贼又在世界各地搞传销了。

某一天我们的圆神终于决定要把QB封印起来了，可是普通的魔法对QB来说是没有用的。于是圆神来到学院都市，找到了呱太医生，呱太医生通过研究，发现QB的构造与人工智能惊人的相似。于是创造出了封印QB的方法。

具体方法是这样的：首先你需要把QB抓过来（笑）。然后通过计算机向QB输入一串由01构成的机器代码，重构QB脑中的意识。可是有一个很严重的问题，就是在输入的代码中，有一个关键位置十分容易被QB现存的意识破坏掉，所以呱太医生必须找到这个位置让圆神为其添加一层护盾，现在呱太医生将这个任务交给了你，你能帮呱太医生找出这个关键位置，拯救世界吗？

那么什么位置算是关键位置呢？，呱太医生告诉说，如果我们吧01串从某个位置分开成两个串，我们把前面的串叫串1，后面的那个叫串2。如果串1中0的个数，等于串2中1的个数。那么这个位置就是关键位置。

注意：因为关键位置没有下标，这里我们用串1最后一个数字的下标来代替表示关键位置（原始01机器代码的下标从1开始），如果觉得我没讲明白的话就看样例和下面的Hint

输入

第一行， 一个n，01串的长度

数据范围：（2 <= n <= 1000000）

第二行，一个01串s

输出

一个数，第一个串最后一个数字的下标

样例输入 复制 

9
000010111

样例输出 复制 

4

提示

样例：这个串可以从关键位置分割成两个串，串1:0000， 串2:10111，为了方便表示关键位置，我们用第一个串的最后一个数字的下标代替关键位置输出。所以输出串1中最后一个0的位置，也就是4。
特殊的：如果一个串中没有出现过1（比如串：0000），请输出0.

来源/分类