내 뒤에 나와 다른 수

면접 대비

시간 제한1초메모리 제한1024 MB

요약

각 위치 i마다 i보다 뒤에 있으면서 A[i]와 값이 다른 가장 작은 인덱스 j를 출력하고, 없으면 -1을 출력한다.

난이도: 보통10점 중 4점
유형: 배열, 구현, 그리디
정답자: 아직 제출이 없습니다

문제

길이가 $N$ 인 수열 $A\_1 \ A\_2 \ \cdots \ A\_N$ 이 주어진다. $1\le i \le N$ 인 정수 $i$ 마다 $i < j \le N$ 이고 $A\_i \ne A\_j$ 인 정수 $j$ 중 최솟값을 출력하라. 만약 이러한 $j$ 가 없다면 $-1$ 을 출력하라.

입력

첫째 줄에 수열 $A$ 의 크기 $N$ 이 주어진다. 둘째 줄에는 $A\_1 \ A\_2 \ \cdots \ A\_N$ 이 공백으로 구분되어 주어진다. $(1 \le N \le 10^6$ , $-10^9 \le A\_i \le 10^9 )$

입력으로 주어지는 모든 수는 정수이다.

출력

각 $i$ 마다 조건을 만족하는 최솟값 $j$ 를 출력하라. 만약 이러한 $j$ 가 없다면 $-1$ 을 출력하라.

예제1

예제 1
입력
```
6
3 3 1 1 4 4
```
예상 출력
```
3 3 5 5 -1 -1
```