分数: 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.
- 让 B_i 是之前的最新位置 i 其中元素等于 A_i 出现。如果这样的位置不存在,则让 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