CF1408H Rainbow Triples

给定一个非负整数序列 $a_1, a_2, \ldots, a_n$。 你需要找到最大的整数 $m$，使得存在 $m$ 个三元组 $(i_1, j_1, k_1)$，$(i_2, j_2, k_2)$，…，$(i_m, j_m, k_m)$，满足： - 对于每个 $p$，$1 \leq i_p < j_p < k_p \leq n$； - $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$，表示你能找到的满足条件的三元组的最大数量。

在前两个测试用例中，元素数量不足以组成一个三元组，因此答案为 $0$。 在第三个测试用例中，可以选择一个三元组 $(1, 2, 3)$。 在第四个测试用例中，可以选择两个三元组 $(1, 3, 5)$ 和 $(2, 4, 6)$。 在第五个测试用例中，可以选择一个三元组 $(1, 2, 3)$。不能选择两个三元组 $(1, 2, 3)$ 和 $(4, 5, 6)$，因为 $a_2 = a_5$。 由 ChatGPT 4.1 翻译