N개의 정수로 구성된 배열이 주어진다.

배열의 각 위치 i에서 오른쪽 방향을 탐색할 때, 해당 위치의 값 A[i]를 처음으로 초과하는 값을 '우측 초과값'이라 정의한다.

우측 초과값이 존재하지 않으면 -1로 처리한다.

모든 위치에 대한 우측 초과값을 배열의 순서대로 출력하라.

입력 설명

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

출력 설명

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

예제 입력 1

4
3 5 2 7

예제 출력 1

5 7 7 -1

예제 입력 2

4
9 5 4 8

예제 출력 2

-1 8 8 -1