C - Repeating Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

長さ 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 を次のように定義する：
    • A_i と等しい要素が i の直前に出現した位置を B_i とする。そのような位置が存在しなければ B_i=-1 とする。
      より正確には、正整数 j であって，A_i = A_j となる j < i が存在するならば、そのうち最大の j を B_i とする。そのような 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行に出力せよ。

入力例 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

Score : 300 points

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