In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of December 7th
(this exercise will still be available for submission after that deadline, but without couting towards your grade)
[to understand the context of this problem, you should read the class #08 exercise sheet]


[AED042] Life Moments

Arthur Dent already knows that 42 is the answer to the ultimate question of life, the universe, and everything, but he just can't stop thinking about the meaning of life. In his quest for self-discovery, he has started to keep track of significant life moments. He records these moments in a sequence, one after another, as he goes through his day. However, Arthur is a bit forgetful, and he frequently wonders if something similar has already happened to him before....

For each new event in his day, Arthur tries to recall the most recent time he experienced something similar. If he remembers a previous, similar event, he notes the position of that memory. If not, he just writes down -1.

The Problem

Given a sequence of Arthur's life events (given as integer identifiers), find out where each event has last occurred before, if at all. For each event in the sequence, record the most recent previous occurrence of that exact event. If it’s the first time Arthur has experienced it, mark it as -1.

Input

The first line of the input contains an integer N, the number of events Arthur has recorded. The second line contains N integers A1, A2, ..., AN, representing the sequence of Arthur's life events. Each number represents a unique kind of event.

Output

The output should consist of one line with a sequence of integers B, where each element Bi represents the last position where the event Ai previously appeared in Arthur’s day. If it’s the first occurrence, print -1 for that position. There should be a single space between elements, but no extra spaces at the start or end of the line.

The first example includes a detailed explanation of the output.

Constraints

The following limits are guaranteed in all the test cases that will be given to your program:

1 ≤ N ≤ 105       Number of events
1 ≤ Ai ≤ 109       Identifier of each event

Example Input 1 Example Output 1
5
1 2 1 1 3
-1 -1 1 3 -1

Explanation of Example Input 1:


Example Input 2 Example Output 2
4
1 1000000000 1000000000 1
-1 -1 2 1


Algorithms and Data Structures (L.EIC011) 2024/2025
DCC/FCUP & DEI/FEUP - University of Porto