CF1945C Left and Right Houses

在 Letovo 村，有 $ n $ 坐房屋。村民们决定修一条大路，把村子分成左右两部分。每个居民都想住在街道的右边或左边，这被描述为一个顺序 $ a_1, a_2, \dots, a_n $，其中 $ a_j = 0 $ 表示编号为 $ j $ 房子的居民想住在街道的左边；否则，$ a_j = 1 $。 这条路将穿过两座房子之间。它左边的房子将被宣布为左边，右边的房子将被宣布为右边。更正式的说法是，**若道路在房屋 $ i $ 和 $ i+1 $ 之间通行。那么，位于 $ 1 $ 和 $ i $ 之间的房屋将位于街道的左侧，位于 $ i+1 $ 和 $ n $ 之间的房屋将位于街道的右侧**。这条路也**可以在第一所房子前面经过，在最后一所房子后面经过**。在这种情况下，整个村庄分别被声明为右侧或左侧。 为了使设计公平，决定铺设道路，使村庄两边至少有一半的居民对选择感到满意。也就是说，在每一边的 $ x $ 个居民中，至少 $ \lceil\frac{x}{2}\rceil $ 应该想住在另一边，其中 $ \lceil x \rceil $ 表示四舍五入的实数 $ x $。 [](https://cdn.luogu.com.cn/upload/vjudge＿pic/CF1945C/2ed555a735574721378598482dfea8442c0609da.png) 路的左边会有 $ i $ 栋房子，对应的 $ a_j $ 中至少有 $ \lceil\frac{i}{2}\rceil $ 个 $0$。在道路的右侧，将会有 $ n-i $ 房屋，在相应的 $ a_j $ 中必须至少有 $ \lceil\frac{n-i}{2}\rceil $ 房屋。确定道路应该铺设在哪座房子 $ i $ 之后，以满足所描述的条件，并尽可能靠近村庄的中心。正式地说，在所有合适的位置 $ i $ 中，最小化 $ \left|\frac{n}{2} - i\right| $（**注意：这里的 $\frac{n}{2}$ 不做取整操作**）。 如果有多个适合的位置 $ i $ 和最小的 $ \left|\frac{n}{2} - i\right| $，输出较小的位置（即更靠左的位置）。

每个测试包含多个测试用例。第一行包含测试用例的数量 $ t $ ($ 1 \le t \le 2\cdot 10^4 $)。下面是测试用例的描述。 每个测试用例的第一行包含一个整数 $ n $ ($ 3 \le n \le 3\cdot 10^5 $)。每个测试用例的下一行包含一个长度为 $ n $ 的字符串 $ a $，仅由 $ 0 $ 和 $ 1 $ 组成。 可以保证所有测试用例 $ n $ 的总和不超过 $ 3\cdot 10^5 $。

对于每个测试用例，输出一个数字 $ i $ ——应该在房子之后铺设道路的位置（如果应该在第一个房子之前铺设道路，则输出 $ 0 $）。我们可以证明答案总是存在的。

让我们考虑输入数据的第一个示例。 如果我们在第一所房子之后铺设道路，将会有一所房子 $ a_1 = 1 $ 在街道的左侧，其中的居民愿意住在街道的右侧。然后 $ 0 $ 出 $ 1 $ 居民在均匀的一边会满意的选择，这意味着道路不能在房子 $ 1 $ 后铺设。 如果我们在第二所房子之后铺设道路，左侧的 $ 2 $ 个居民中的 $ 1 $ 位（$ a_1 = 1 $, $ a_2 = 0 $）和右侧 $ 1 $ 位居民中的 $ 1 $ 位（$ a_3 = 1 $）将对选择感到满意。两边一半以上的居民都对这个选择感到满意，这意味着这条路可以能在房子 $ 2 $ 后铺设。我们可以证明这是最优答案。 翻译者：[SCAR_L](https://www.luogu.com.cn/user/608703)