← 返回题目列表

AtCoder · abc378_c

F. 重复

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

分数: 300 点

问题陈述

给你一系列 N 正数, A = (A_1, A_2, \dots, A_N)。找到序列 B = (B_1, B_2, \dots, B_N) 长度 N 定义如下。

  • 对于 i = 1, 2, \dots, N,定义 B_i 如下:
    • 让 B_i 是之前的最新位置 i 其中元素等于 A_i 出现。如果这样的位置不存在,则让 B_i = -1.
      更准确地说,如果存在正整数 j 这样 A_i = A_j 和 j < i,让 B_i 成为最大的此类 j。如果没有这样的 j 存在,令 B_i = -1.

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 所有输入值均为整数。

输入

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

N
A_1 A_2 \dots A_N

输出

打印以下元素 B 位于一行,以空格分隔。


示例输入 1

5
1 2 1 1 3

示例输出 1

-1 -1 1 3 -1
  • i = 1:没有 1 之前 A_1 = 1,所以 B_1 = -1.
  • i = 2:没有 2 之前 A_2 = 2,所以 B_2 = -1.
  • i = 3:最近发生的 1 之前 A_3 = 1 is A_1,所以 B_3 = 1.
  • i = 4:最近发生的 1 之前 A_4 = 1 is A_3,所以 B_4 = 3.
  • i = 5:没有 3 之前 A_5 = 3,所以 B_5 = -1.

示例输入 2

4
1 1000000000 1000000000 1

示例输出 2

-1 -1 2 1