← 返回题目列表

AtCoder · arc195_d

D. 交换和擦除

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

分数: 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 在三个或更少的操作中清空。