B. Расселение морских свинок
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даша очень любит морских свинок. В связи с этим, она решила поселить как можно больше морских свинок у себя дома и разработала план на ближайшие $$$n$$$ дней. Каждый день она будет либо покупать новую морскую свинку, либо вызывать врача, чтобы он осмотрел всех ее питомцев.

К сожалению, магазин, в котором она собралась покупать морских свинок, не разбирается в них. Поэтому не может определить их пол. Даша тоже не может этого сделать. Единственный, кто может помочь — врач.

Для содержания морских свинок нужны вольеры. Покупать их Даша планирует в том же магазине. К сожалению, там продается только один вид — двухместный вольер. В нем может жить не более двух морских свинок.

Так как Даша не хочет нанести моральную травму своим питомцам — она не будет селить двух морских свинок разного пола в один вольер.

Помогите Даше посчитать, сколько минимум вольеров нужно купить, чтобы ни в один момент времени две морские свинки разных полов не жили в одном вольере.

В рамках этой задачи мы считаем, что у морских свинок всего два пола — мужской и женский.

Входные данные

В первой строке входных данных дано одно число $$$t$$$ ($$$1 \leqslant t \leqslant 10^5$$$) — количество наборов входных данных.

В первой строке каждого набора входных данных дано одно число $$$n$$$ ($$$1 \leqslant n \leqslant 10^5$$$) — количество дней на которые у Даши есть план.

В следующей строке дано $$$n$$$ чисел $$$b_1, b_2, b_3, \ldots, b_n$$$ ($$$1 \leqslant b_i \leqslant 2$$$) — план Даши. Если $$$b_i = 1$$$, то в $$$i$$$-й день Даша купит новую морскую свинку. Если $$$b_i = 2$$$, то в $$$i$$$-й день к Даше придет доктор и поможет определить пол всех морских свинок которые уже есть у Даши.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно число — сколько минимум вольеров нужно купить Даше, чтобы ни в один момент времени две морские свиньи разного пола не жили вместе.

Пример
Входные данные
6
3
1 1 1
3
2 2 2
5
1 1 1 2 1
10
1 2 1 2 1 2 1 2 1 2
20
1 2 1 1 1 1 1 2 1 2 1 2 2 1 1 1 1 1 1 1
20
2 1 1 2 1 1 2 1 2 2 1 1 1 2 2 1 1 1 1 2
Выходные данные
3
0
3
4
12
9
Примечание

В первом наборе входных данных Даше нужно селить каждую морскую свинку в отдельный вольер, так как она не знает их пол.

Во втором наборе входных данных Даша купит $$$0$$$ морских свинок, а значит ей потребуется $$$0$$$ вольеров.

В третьем наборе входных данных Даше нужно $$$3$$$ вольера, чтобы поселить каждую морскую свинку в отдельный вольер до прихода врача на $$$4$$$-й день. Когда она узнает их пол, то хотя бы две морские свинки окажутся одного пола и их можно будет поселить в один вольер, а третью - в другой вольер. Таким образом у нее будет один свободный вольер, в который она может поселить новую морскую свинку. Таким образом ответ $$$3$$$.

В четвертом наборе входных данных покажем, что $$$4$$$ - оптимальный ответ.

Для начала заметим, что первые четыре морские свинки можно поселить по одной в вольер. Затем придет врач и определит их пол. Среди этих четырех морских свинок будет хотя бы одна пара одного пола, потому что: либо морских свинок мужского пола хотя бы $$$2$$$, либо их не больше $$$1$$$, а значит женского пола хотя бы $$$3$$$. Теперь мы можем поселить эту пару в один вольер, а две остальные - в отдельные. У нас останется еще один пустой вольер куда можно поселить новую свинку.

Теперь покажем, что ответ не меньше $$$4$$$. Пусть среди первых $$$4$$$ морских свинок $$$3$$$ имеют женский пол и $$$1$$$ - мужской. Нам нужно минимум $$$3$$$ вольера чтобы их расселить. Тогда, когда мы купим новую морскую свинку - нам понадобится еще один вольер, в которые мы ее поселим, так как мы не знаем ее пол.