分数: 700 点
问题陈述
有一个序列 A = (A_1,\ldots,A_N)。您可以按任意顺序执行任意次数的以下两种类型的操作:
- 让 K 的长度 A 就在操作之前。选择一个整数 i 这样 1 \leq i \leq K-1,并交换 i-th 和 (i+1)第一个元素 A.
- 让 K 的长度 A 就在操作之前。选择一个整数 i 这样 1 \leq i \leq K 以及来自 1-st 通过 i第一个元素 A 相等,并删除其中的所有元素 1-st 通过 i- 第 A.
找出完成任务所需的最少操作总数 A 一个空序列。
你被给予 T 测试用例;解决它们中的每一个。
约束
- 1\leq T\leq 10^5
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq N
- 总和 N 所有测试用例最多 2\times 10^5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
每个案例均按以下格式给出:
N A_1 A_2 \ldots A_N
输出
按顺序打印每个测试用例的答案,以换行符分隔。
示例输入 1
3 5 1 1 2 1 2 4 4 2 1 3 11 1 2 1 2 1 2 1 2 1 2 1
示例输出 1
3 4 8
对于第一个测试用例, A 可以通过以下三个操作清空:
- 交换第 3 个和第 4 个元素 A。现在, A is (1,1,1,2,2).
- 删除第 1 到第 3 个元素 A。现在, A is (2,2).
- 删除第一个到第二个元素 A。现在, A 是一个空序列。
对于第二个测试用例, A 可以通过删除第一个元素四次将其清空。而且,不可能使 A 在三个或更少的操作中清空。