31631번 - :rightplant: 스페셜 저지

문제

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$을 공백으로 구분하여 출력합니다. 가능한 답이 여러 가지라면 아무거나 출력합니다.

제한

힌트