← 返回题目列表

Codeforces · 2117/C

C. 酷分区

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

Yousef 有一个大小为 $$$n$$$ 的数组 $$$a$$$。他想要将数组划分为一个或多个连续的段,以便每个元素 $$$a_i$$$ 恰好属于一个段。

一个分区被称为 酷 如果对于每个段 $$$b_j$$$,$$$b_j$$$ 中的所有元素也出现在 $$$b_{j + 1}$$$ 中(如果存在)。也就是说,段中的每个元素也必须存在于其后面的段中。

例如,如果 $$$a = [1, 2, 2, 3, 1, 5]$$$,则 a Yousef 可以创建的 酷 分区为 $$$b_1 = [1, 2]$$$, $$$b_2 = [2, 3, 1, 5]$$$。这是一个 酷 分区,因为 $$$b_1$$$ 中的每个元素(即 $$$1$$$ 和 $$$2$$$)也出现在 $$$b_2$$$ 中。相反,$$$b_1 = [1, 2, 2]$$$, $$$b_2 = [3, 1, 5]$$$ 不是 酷 分区,因为 $$$2$$$ 出现在 $$$b_1$$$ 中,但不在 $$$b_2$$$ 中。

请注意,对数组进行分区后,您需要执行以下操作: 不 更改段的顺序。另请注意,如果某个元素在某个段 $$$b_j$$$ 中出现多次,则只需在 $$$b_{j + 1}$$$ 中至少出现一次。

你的任务是帮助 Yousef 找到构成一个的最大分段数 酷 分区。

输入

输入的第一行包含整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 数组的大小。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — 数组的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 — 构成一个测试用例的最大段数 酷 分区。

示例

输入
复制

8
6
1 2 2 3 1 5
8
1 2 1 3 2 1 3 2
5
5 4 3 2 1
10
5 8 7 5 8 5 7 8 10 9
3
1 2 2
9
3 3 1 4 3 2 4 1 2
6
4 5 4 5 6 4
8
1 2 1 2 1 2 1 2

输出
复制

2
3
1
3
1
3
3
4

注意

第一个测试用例在语句中进行了解释。我们可以将其划分为 $$$b_1 = [1, 2]$$$, $$$b_2 = [2, 3, 1, 5]$$$。可以看出没有其他分区具有更多的段。

在第二个测试用例中,我们可以将数组划分为 $$$b_1 = [1, 2]$$$, $$$b_2 = [1, 3, 2]$$$, $$$b_3 = [1, 3, 2]$$$。最大段数为 $$$3$$$。

在第三个测试用例中,我们唯一可以进行的分区是 $$$b_1 = [5, 4, 3, 2, 1]$$$。任何其他分区都不会满足该条件。因此,答案是$$$1$$$。