The Next Different Number

Interview

Time limit1sMemory limit1024 MB

Summary

For each position i in a sequence, find the smallest later index j whose value differs from A[i], or -1 if none exists.

Level: Easy3 of 10
Topics: Array, Implementation, Greedy
Solved: No attempts yet

Problem

A sequence of length $N$ , $A_1 \ A_2 \ \cdots \ A_N$ , is given. For each integer $i$ with $1 \le i \le N$ , output the smallest integer $j$ such that $i < j \le N$ and $A_i \ne A_j$ . If no such $j$ exists, output $-1$ .

Input

The first line gives $N$ , the size of the sequence $A$ . The second line gives $A_1 \ A_2 \ \cdots \ A_N$ separated by spaces. $(1 \le N \le 10^6$ , $-10^9 \le A_i \le 10^9 )$

Every number in the input is an integer.

Output

For each $i$ , output the smallest $j$ that satisfies the condition. If no such $j$ exists, output $-1$ .

Examples1

Example 1
Input
```
6
3 3 1 1 4 4
```
Expected output
```
3 3 5 5 -1 -1
```