题目描述

逍遥村有 $n$ 栋房子。村民们决定修建一条大路，将村子分为左右两边。每个居民都想住在街道的右侧或左侧，这可以用序列 $a_1,a_2,…,a_n$ 来描述，其中 $a_j=0$ 表示位置 $j$ 处房子的居民想住在街道的左侧；否则， $a_j=1$ 。

道路将从两栋房子之间穿过。它左边的房子将被宣布为左侧，右边的房子将被宣布为右侧。更正式地说，让道路从房屋 $i$ 和 $i+1$ 之间通过。那么位于 $1$ 和 $i$ 之间的房屋将位于街道的左侧，位于 $i+1$​ 和 $n$​ 之间的房屋将位于街道的右侧。道路也可以经过第一栋房屋之前和最后一栋房屋之后；在这种情况下，整个村庄分别被宣布为右侧或左侧。

为了使设计公平，我们决定在铺设道路时，至少要让村子两边各一半的居民对选择感到满意。也就是说，在一侧的 $x$ 个居民中，至少有 $⌈\frac {x}{2}⌉$ 个居民愿意住在这一侧，其中 $⌈x⌉$ 表示四舍五入的实数 $x$ 。

确定在哪座房子 $i$ 之后铺设道路，以满足所述条件，并尽可能靠近村庄中央。从形式上看，在所有合适的位置 $i$ 中，尽量减少 $∣\frac {n}{2} - i∣$ 。

如果有多个合适的位置，输出较小的一个。

输入格式

第一行包含一个整数 $n ( 3≤n≤3⋅10^5 )$。每个测试用例的下一行包含一个长度为 $n$ 的字符串 $a$ ，该字符串仅由 $0$ 和 $1$ 组成。

输出格式

输出一个数字 $i$ --道路应该铺设在房屋之后的位置(如果道路应该铺设在第一栋房屋之前，则输出 $0$ )。

样例

样例输入 #1

3
101

样例输出 #1

2

样例输入 #2

6
010111

样例输出 #2

3

提示

样例解释 $1$:

第一栋房屋后铺设道路，那么街道左侧将有一栋房屋 $a_1=1$ ，其居民希望住在街道右侧，不会感到满意，这意味着道路不能铺设在第 $1$ 户之后。

如果我们在第二栋房屋后铺设道路，两边各有一半以上的居民对选择感到满意，这意味着道路可以铺设在房屋 $2$ 之后。这是最优答案。