103782: [Atcoder]ABC378 C - Repeating

Problem Statement

You are given a sequence of $N$ positive numbers, $A = (A_1, A_2, \dots, A_N)$. Find the sequence $B = (B_1, B_2, \dots, B_N)$ of length $N$ defined as follows.

• For $i = 1, 2, \dots, N$, define $B_i$ as follows:
  • Let $B_i$ be the most recent position before $i$ where an element equal to $A_i$ appeared. If such a position does not exist, let $B_i = -1$.
    More precisely, if there exists a positive integer $j$ such that $A_i = A_j$ and $j < i$, let $B_i$ be the largest such $j$. If no such $j$ exists, let $B_i = -1$.

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$
$A_1$ $A_2$ $\dots$ $A_N$

Output

Print the elements of $B$ in one line, separated by spaces.

Sample Input 1

5
1 2 1 1 3

Sample Output 1

-1 -1 1 3 -1

• $i = 1$: There is no $1$ before $A_1 = 1$, so $B_1 = -1$.
• $i = 2$: There is no $2$ before $A_2 = 2$, so $B_2 = -1$.
• $i = 3$: The most recent occurrence of $1$ before $A_3 = 1$ is $A_1$, so $B_3 = 1$.
• $i = 4$: The most recent occurrence of $1$ before $A_4 = 1$ is $A_3$, so $B_4 = 3$.
• $i = 5$: There is no $3$ before $A_5 = 3$, so $B_5 = -1$.

Sample Input 2

4
1 1000000000 1000000000 1

Sample Output 2

-1 -1 2 1

问题陈述

给定一个由$N$个正数组成的序列，$A = (A_1, A_2, \dots, A_N)$。找出长度为$N$的序列$B = (B_1, B_2, \dots, B_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$：在$A_1 = 1$之前没有1，所以$B_1 = -1$。
• $i = 2$：在$A_2 = 2$之前没有2，所以$B_2 = -1$。
• $i = 3$：在$A_3 = 1$之前最近的1是$A_1$，所以$B_3 = 1$。
• $i = 4$：在$A_4 = 1$之前最近的1是$A_3$，所以$B_4 = 3$。
• $i = 5$：在$A_5 = 3$之前没有3，所以$B_5 = -1$。

样本输入 2

4
1 1000000000 1000000000 1

样本输出 2

-1 -1 2 1