← 返回题目列表

Codeforces · 1278/C

C. 浆果果酱

中文机器翻译题面 查看原题

卡尔森最近在房子的地下室发现了大量浆果果酱罐。更具体地说,有 $$$2n$$$ 罐草莓和蓝莓果酱。

所有 $$$2n$$$ 罐子排列成一排。通往地下室的楼梯正好在那排的中间。因此,当卡尔森进入地下室时,他准确地看到左侧有 $$$n$$$ 个罐子,右侧有 $$$n$$$ 个罐子。

例如,地下室可能如下所示:

作为一个正直的人,他立即开始吃果酱。一分钟后,他选择清空左边第一个非空罐子或右边第一个非空罐子。

最后,Karlsson 决定最后装满的草莓和蓝莓果酱罐的数量应该相同。

例如,结果可能是:

他吃了左边的 $$$1$$$ 罐子,然后吃了右边的 $$$5$$$ 罐子。还剩下$$$3$$$满罐的草莓和蓝莓果酱。

罐子从左到右编号为 $$$1$$$ 到 $$$2n$$$,因此 Karlsson 最初站在罐子 $$$n$$$ 和 $$$n+1$$$ 之间。

Karlsson 需要清空的最少罐子数量是多少,才能留下相同数量的满草莓和蓝莓果酱罐?

你的程序应该回答 $$$t$$$ 独立测试用例。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$)。

每个测试用例的第二行包含 $$$2n$$$ 整数 $$$a_1, a_2, \dots, a_{2n}$$$ ($$$1 \le a_i \le 2$$$) — $$$a_i=1$$$ 表示左边第 $$$i$$$ 罐子是草莓酱罐子,$$$a_i=2$$$意思是它是一个蓝莓果酱罐。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,请打印答案 - Karlsson 需要清空的最小罐子数量,以便留下相同数量的满草莓和蓝莓果酱罐。

示例

输入 #1

4
6
1 1 1 2 2 1 2 1 2 1 1 2
2
1 2 1 2
3
1 1 1 1 1 1
2
2 1 1 1

输出 #1

6
0
6
2

注意

声明中的图片描述了第一个测试用例。

在第二个测试用例中,草莓果酱罐和蓝莓果酱罐的数量已经相等。

在第三个测试用例中,Karlsson 需要吃掉所有 $$$6$$$ 罐子,以便剩下 $$$0$$$ 罐子的两种果酱。

在第四个测试用例中,Karlsson 可以清空第二个和第三个罐子,或者第三个和第四个罐子。这两种情况都会留下 $$$1$$$ 罐两种果酱。