탑 보기

면접 대비

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

요약

각 건물에서 왼쪽과 오른쪽으로 보이는 건물의 수를 세고, 가장 가까운 보이는 건물의 번호를 출력한다. 키가 같거나 작은 건물은 더 큰 건물에 가려 보이지 않는다.

문제

일직선 위에 높이가 제각각인 건물 $N$ 개가 있다. 각 건물의 옥상에서 양옆을 바라볼 때 건물의 옆면이 몇 개 보이는지 알아보려 한다.

$i$ 번째 건물을 기준으로 $i - 1$ , $i - 2$ , ..., $1$ 번째 건물은 왼쪽에 있고, $i + 1$ , $i + 2$ , ..., $N$ 번째 건물은 오른쪽에 있다. 이웃한 건물 사이의 거리는 모두 같다.

지금 있는 건물의 높이가 $L$ 이라고 하자. 높이가 $L$ 보다 큰 건물만 볼 수 있다.

바라보는 방향에서 높이가 $L$ 인 건물 뒤에 높이가 $L$ 이하인 건물이 있으면 그 건물은 가려져 보이지 않는다.

각 건물에서 볼 수 있는 건물이 무엇인지 구해보자.

첫 번째 줄에 건물의 개수 $N$ 이 주어진다.

두 번째 줄에는 $N$ 개의 건물 높이가 공백으로 구분되어 주어진다.

$i(1 \le i \le N)$ 번째 건물에서 볼 수 있는 건물의 개수를 출력한다.

만약 볼 수 있는 건물의 개수가 1개 이상이라면 $i$ 번째 건물에서 거리가 가장 가까운 건물의 번호 중 작은 번호로 출력한다.

예제 1

입력

8
3 7 1 6 3 5 1 7

예상 출력