Seta는 CCO를 위한 문제를 만들고 있습니다! 그녀는 다음과 같은 문제를 생각해냈습니다.

값의 범위가 $[1, N]$인 배열 $A[1, \dots, N]$이 주어졌을 때, $\ell \le i \le r$을 만족하는 모든 쌍 $(\ell, r)$의 개수를 $B[i]$라고 정의합니다. 이때, $$A[i] = \min(A[\ell], A[\ell+1], \dots, A[r-1], A[r])$$ 입니다.

배열 $B[1, \dots, N]$을 출력하세요.

하지만 CCO 전날, Seta의 컴퓨터가 고장 나서 출력 파일만 복구할 수 있었습니다. 출력 배열 $B[1, \dots, N]$이 주어졌을 때, 입력 배열 $A[1, \dots, N]$을 복원하는 프로그램을 작성할 수 있을까요?

Seta는 배열 $A$가 반드시 유일하지는 않으며, 유효한 배열이라면 무엇이든 정답으로 인정한다고 알려주었습니다.

입력

첫 번째 줄에는 정수 $N$이 주어집니다. 두 번째 줄에는 $N$개의 정수 $B[1], \dots, B[N]$이 공백으로 구분되어 주어집니다 ($1 \le B[i] \le N^2$).

다음 표는 25점의 배점이 어떻게 분배되는지 보여줍니다.

출력

$1 \le A[i] \le N$을 만족하는 $N$개의 정수, 배열 $A[1], \dots, A[N]$을 공백으로 구분하여 출력하세요. 항상 적어도 하나의 유효한 배열 $A$가 존재함이 보장됩니다.

만약 유효한 배열이 여러 개 있다면, 그중 아무거나 출력해도 됩니다. 특히, 원래 배열 $A$가 순열이었더라도, 출력하는 답이 반드시 순열일 필요는 없습니다.

예제

예제 입력 1

3
3 1 2

예제 출력 1

1 3 2

참고

예제 1의 출력에 대한 설명: 부분 배열 $[1, 3, 2], [1, 3], [1]$의 최솟값은 $1$입니다. 이러한 부분 배열은 $3$개입니다. 부분 배열 $[3]$의 최솟값은 $3$입니다. 이러한 부분 배열은 $1$개입니다. * 부분 배열 $[3, 2]$와 $[2]$의 최솟값은 $2$입니다. 이러한 부분 배열은 $2$개입니다.

예제 입력 2

2
2 2

예제 출력 2

1 1

예제 입력 3

3
1 4 1

예제 출력 3

2 1 3

참고

예제 3의 출력에 대한 설명: $A = [2, 1, 2]$인 경우도 정답으로 인정됩니다.