R00761
오큰수
골드 IV레이팅
의견: 0
설명
크기가 \(N\)인 수열 \(A_1, A_2, \dots, A_N\)이 있다. 수열의 각 원소 \(A_i\)에 대해 오큰수 \(\mathrm{NGE}(i)\)를 구하려고 한다.
\(A_i\)의 오큰수는 \(A_i\)보다 오른쪽에 있으면서 \(A_i\)보다 큰 수 중 가장 왼쪽에 있는 수를 뜻한다. 그러한 수가 없으면 오큰수는 \(-1\)이다.
예를 들어 \(A = [3, 5, 2, 7]\)이면 오큰수는 차례로 \(5, 7, 7, -1\)이다.
제약
\(1 \le N \le 500\,000\), \(1 \le A_i \le 1\,000\,000\).
입력 형식
첫째 줄에 수열의 크기 \(N\)이 주어진다. 둘째 줄에 수열의 원소 \(A_1, A_2, \dots, A_N\)이 주어진다.
출력 형식
\(N\)개의 수 \(\mathrm{NGE}(1), \dots, \mathrm{NGE}(N)\)을 공백으로 구분해 출력한다.
예제 1
입력
4
3 5 2 7
출력
5 7 7 -1
설명
3의 오큰수는 5, 5의 오큰수는 7, 2의 오큰수는 7, 7은 없으므로 -1.
예제 2
입력
4
9 5 4 8
출력
-1 8 8 -1
문제 정보
riseoj 작성
출처 Original
태그
평가 및 의견
오큰수
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
오큰수
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기