← 返回题目列表

AtCoder · abc306_c

E. 中心

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

分数: 250 点

问题陈述

给你一个序列 A=(A_1,A_2,\dots,A_{3N}) 长度 3N 其中每个 1,2,\dots,和 N 恰好出现了 3 次。

对于 i=1,2,\dots,N,让 f(i) 是中间出现的索引 i in A。 排序 1,2,\dots,N 按升序排列 f(i).

正式地, f(i) 定义如下。

  • 假设那些 j 这样 A_j = i 是 j=\alpha,\beta,\gamma\ (\alpha < \beta < \gamma)。 然后, f(i) = \beta.

约束

  • 1\leq N \leq 10^5
  • 1 \leq A_j \leq N
  • i 发生于 A 正好三次,每个 i=1,2,\dots,N.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \dots A_{3N}

输出

打印长度序列 排序得到 N 通过排序得到 1,2,\dots,N 按升序排列 f(i),用空格分隔。


示例输入 1

3
1 1 3 2 3 2 2 3 1

示例输出 1

1 3 2
  • 1 发生于 A at A_1,A_2,A_9,所以 f(1) = 2.
  • 2 发生于 A at A_4,A_6,A_7,所以 f(2) = 6.
  • 3 发生于 A at A_3,A_5,A_8,所以 f(3) = 5.

因此, f(1) < f(3) < f(2),所以 1,3,和 2 应按此顺序打印。


示例输入 2

1
1 1 1

示例输出 2

1

示例输入 3

4
2 3 4 3 4 1 3 1 1 4 2 2

示例输出 3

3 4 1 2