分数: 500 点
问题陈述
有 2N 宝石从左到右排列成一排,以及宝石的类型 i左边第一个宝石是 A_i。在这里, A_i 是介于 1 和 N,包含在内,并且每种类型恰好有两颗宝石。
您想要插入满足以下条件的分隔线。
- 每个分隔符的位置由一个整数表示 i (1 \le i \le 2N - 1),这意味着它在 i-th 和 (i+1)左起第 颗宝石。
- 同一位置不存在两个或多个分隔线。
- 分隔线数量 K 最多是 N.
- 插入 K 分隔线将宝石行分为 K + 1 段。在这里,收集左侧奇数(第一、第三……)段中的所有宝石会产生每种类型的恰好一个宝石 1, 2, \ldots, N.
输出一种插入满足此条件的分隔符的方式。可以证明这样的方式总是存在的。
你被给予 T 测试用例;逐一解决。
约束
- 1 \le T \le 10^5
- 1 \le N \le 2 \times 10^5
- 1 \le A_i \le N (1 \le i \leq 2N)
- 每种类型恰好有两颗宝石。也就是说,对于每个 x (1 \le x \le N),正好有两个索引 i 与 A_i = x.
- 总和 N 所有测试用例最多 2 \times 10^5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
每个测试用例均按以下格式给出:
N
A_1 A_2 \ldots A_{2N}
输出
输出 T 测试用例按顺序排列。
对于每个测试用例,输出一种插入满足条件的分隔符的方法。 具体来说,让 K 是分隔线的数量, C_1, C_2, \ldots, C_K 为分隔符的位置,按升序排列,并按以下格式输出:
K C_1 C_2 \ldots C_K
在这里, K 最多必须是 N.
样本输入 1
2 3 1 2 2 3 3 1 5 1 2 3 4 5 5 4 3 2 1
示例输出 1
3 1 2 4 1 5
对于第一个测试用例,在位置插入分隔符 1, 2, 4 将宝石分成几段 (1),(2),(2,3),(3,1),并收集左侧奇数段中的所有宝石,每种类型恰好产生一颗宝石 1, 2, 3.