H. Разноцветные тройки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана последовательность $$$a_1, a_2, \ldots, a_n$$$ неотрицательных целых чисел.

Вам нужно найти наибольшее число $$$m$$$ троек $$$(i_1, j_1, k_1)$$$, $$$(i_2, j_2, k_2)$$$, ..., $$$(i_m, j_m, k_m)$$$ таких, что выполняются следующие условия:

  • $$$1 \leq i_p < j_p < k_p \leq n$$$ для всех $$$p$$$ среди $$$1, 2, \ldots, m$$$;
  • $$$a_{i_p} = a_{k_p} = 0$$$, $$$a_{j_p} \neq 0$$$;
  • значения $$$a_{j_1}, a_{j_2}, \ldots, a_{j_m}$$$ различны;
  • значения $$$i_1, j_1, k_1, i_2, j_2, k_2, \ldots, i_m, j_m, k_m$$$ различны.
Входные данные

В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 500\,000$$$): количество наборов входных данных.

В первой строке каждого набора входных данных находится одно целое число $$$n$$$ ($$$1 \leq n \leq 500\,000$$$).

Во второй строке находятся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq n$$$).

Сумма по всем $$$n$$$ не превосходит $$$500\,000$$$.

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

Для каждого набора выходных данных выведите одно целое число $$$m$$$: наибольшее количество троек, которое вы можете найти.

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

В первых двух примерах не хватает элементов даже для одной тройки, так что ответ $$$0$$$.

Во втором примере вы можете выбрать одну тройку $$$(1, 2, 3)$$$.

В четвертом примере можно выбрать две тройки $$$(1, 3, 5)$$$ и $$$(2, 4, 6)$$$.

В пятом примере можно выбрать одну тройку $$$(1, 2, 3)$$$. Мы не можем выбрать тройки $$$(1, 2, 3)$$$ и $$$(4, 5, 6)$$$ одновременно, так как $$$a_2 = a_5$$$.