← 返回题目列表

Codeforces · 1408/H

H. 彩虹三元组

中文机器翻译题面 查看原题

给定一个非负整数序列 $$$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$$$。