Вам дана последовательность \(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\) различны.
Выходные данные
Для каждого набора выходных данных выведите одно целое число \(m\): наибольшее количество троек, которое вы можете найти.
Примечание
В первых двух примерах не хватает элементов даже для одной тройки, так что ответ \(0\).
Во втором примере вы можете выбрать одну тройку \((1, 2, 3)\).
В четвертом примере можно выбрать две тройки \((1, 3, 5)\) и \((2, 4, 6)\).
В пятом примере можно выбрать одну тройку \((1, 2, 3)\). Мы не можем выбрать тройки \((1, 2, 3)\) и \((4, 5, 6)\) одновременно, так как \(a_2 = a_5\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|