Rightplant

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

요약

N이 주어질 때, 높이 1부터 N까지를 한 번씩 사용한 건물 배열 중 모든 시작 건물에서 쏜 가지의 방향 전환 횟수 합이 최대가 되는 배열을 구합니다.

난이도: 어려움10점 중 8점
유형: 배열, 시뮬레이션, 그리디
정답자: 아직 제출이 없습니다

문제

$1$ 부터 $N$ 까지의 서로 다른 정수 높이를 가진 $N$ 개의 빌딩이 일렬로 놓여 있습니다. 왼쪽에서 $i$ 번째 빌딩의 높이는 $H_i$ 입니다.

높이 $h$ 인 빌딩에서 가지를 오른쪽으로 발사하면, 가지는 높이 $h$ 이하인 빌딩의 위를 통과하여 날아갑니다. 가지가 높이 $h$ 초과인 빌딩에 부딪히면 그 빌딩의 높이를 $1$ 줄이고 진행 방향을 반대로 바꿉니다.

높이 $h$ 인 빌딩에서 오른쪽으로 날아가는 가지가 높이 $h$ 미만인 빌딩의 위를 통과하는 모습

높이 $h$ 인 빌딩에서 오른쪽으로 날아가는 가지가 높이 $h$ 인 빌딩의 위를 통과하는 모습

높이 $h$ 인 빌딩에서 오른쪽으로 날아가는 가지가 높이 $h$ 초과인 빌딩에 부딪혀 방향을 바꾸는 모습

왼쪽에서 $i$ 번째 빌딩에서 가지를 오른쪽으로 발사합니다. 이 가지가 맨 왼쪽 또는 맨 오른쪽 빌딩을 통과하여 날아갈 때까지 진행 방향을 바꾼 횟수를 $B_i$ 라 합시다. $B_1 + B_2 + \dots + B_N$ 의 값이 최대가 되도록 하는 수열 $H$ 를 구해 봅시다.

입력

첫 번째 줄에 정수 $N$ 이 주어집니다. ( $2 \le N \le 5\,000$ )

출력

첫 번째 줄에 $B_1 + B_2 + \dots + B_N$ 의 값이 최대가 되도록 하는 수열 $H$ 의 원소 $H_1, H_2, \dots, H_N$ 을 공백으로 구분하여 출력합니다. 가능한 답이 여러 가지라면 아무거나 출력합니다.

예제1

예제 1
입력
```
2
```
예상 출력
```
1 2
```