Карлсон недавно обнаружил огромные запасы ягодного варенья в подвале дома. Если точнее, то там оказались $$$2n$$$ банок клубничного и черничного варенья.
Все $$$2n$$$ банок расставлены в ряд. Лестница в подвал находится ровно в середине этого ряда. Поэтому, когда Карлсон спускается в подвал, он видит ровно $$$n$$$ банок слева и $$$n$$$ банок справа.
Например, подвал может выглядеть следующим образом:
Карлсон — очень прямолинейный молодой человек, поэтому он сразу начинает есть варенье. За одну минуту он опустошает либо первую непустую банку слева, либо первую непустую банку справа.
Наконец, Карлсон решил, что в конце процесса должно остаться равное количество банок с клубничным и черничным вареньем.
Например, результат может быть таким:
Он съел $$$1$$$ банку слева, а затем $$$5$$$ банок справа. Осталось ровно по $$$3$$$ полных банки клубничного и черничного варенья. Банки пронумерованы от $$$1$$$ до $$$2n$$$ слева направо, так что Карлсон начинает между банками $$$n$$$ и $$$n+1$$$.
Какое минимальное число банок Карлсону придется опустошить, чтобы осталось равное количество банок с клубничным и черничным вареньем?
Вам нужно ответить на $$$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$$$.
На каждый набор входных данных выведите ответ — минимальное количество банок, которые Карлсону придется опустошить, чтобы осталось равное количество банок с клубничным и черничным вареньем.
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
6 0 6 2
На картинке описывается первый набор входных данных.
Во втором наборе входных данных количества банок с клубничным и с черничным вареньем уже совпадают.
В третьем наборе входных данных Карлсону придется съесть все $$$6$$$ банок, так чтобы осталось $$$0$$$ банок каждого варенья.
В четвертом наборе входных данных Карлсон может либо опустошить вторую и третью банки, либо третью и четвертую. В обоих случаях останется по $$$1$$$ банке каждого варенья.
