내 뒤에 나와 다른 수

면접 대비

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

요약

수열의 각 위치 i에 대해 A[i]와 다른 값을 가진 가장 가까운 뒤쪽 인덱스 j를 구하고, 없으면 -1을 출력한다.

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

문제

길이가 $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
```