给定一个非负整数序列 $$$a_1, a_2, \ldots, a_n$$$。
您需要找到三元组 $$$(i_1, j_1, k_1)$$$, $$$(i_2, j_2, k_2)$$$, ..., $$$(i_m, j_m, k_m)$$$ 的最大数量 $$$m$$$,这样:
- $$$1 \leq i_p < j_p < k_p \leq n$$$ 对于 $$$1, 2, \ldots, m$$$ 中的每个 $$$p$$$;
- $$$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$$$:您可以找到的最大正确三元组数。
示例
输入 #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
输出 #1
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$$$。