Мариса — девушка с принципами, она всегда помогает другим беречь их вещи. В течение $$$n$$$ дней она каждый день приходит и забирает обед для Рейму. $$$i$$$-й обед описывается своей вкусностью — целым числом $$$w_i$$$ ($$$0\le w_i\le 2$$$), образуя последовательность $$$w$$$ длины $$$n$$$.
Мариса особенно любит число $$$3$$$. Она может выполнить следующую операцию ноль или более раз:
Определите максимальное число операций, которое может выполнить Мариса.
$$$^{\text{∗}}$$$Последовательность $$$a$$$ является подпоследовательностью $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) элементов на произвольных позициях.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
В первой строке каждого набора входных данных дано одно целое число $$$n$$$ ($$$1\le n \le 100$$$).
Во второй строке даны $$$n$$$ целых чисел $$$w_1, w_2, \ldots, w_n$$$ ($$$0\leq w_i \leq 2$$$), обозначающие значения вкусности обедов.
Для каждого набора входных данных выведите максимальное число операций, которое может выполнить Мариса.
340 0 0 031 2 051 2 1 2 1
422
В первом наборе входных данных Мариса может выполнить четыре операции: $$$$$$[\underline{0},0,0,0]\to[\underline{0},0,0]\to[\underline{0},0]\to[\underline{0}]\to [].$$$$$$
Во втором наборе входных данных Мариса может выполнить две операции: $$$$$$[\underline{1},\underline{2},0]- \gt [\underline{0}]- \gt [].$$$$$$
В третьем наборе входных данных Мариса может выполнить две операции: $$$$$$[\underline{1},2,1,\underline{2},1]- \gt [\underline{2},1,\underline{1}]- \gt [1].$$$$$$
| Codeforces Round 1098 (Div. 2) |
|---|
| Закончено |
