수조 사이의 한 번 이동

문제

한 수족관의 관리실에는 같은 종류의 작은 물고기를 돌보는 수조 N개가 일렬로 놓여 있다. 수조에는 왼쪽부터 1번부터 N번까지 번호가 붙어 있다. 관리자는 물고기가 한쪽 수조에 지나치게 모이지 않도록, 수조 사이의 연결 통로를 이용하는 이동 작업을 딱 한 번 진행하려 한다. 작업을 시작하기 직전에 i번 수조에 들어 있는 물고기 수는 A_i마리이다. 각 수조는 바로 왼쪽 수조와 바로 오른쪽 수조만 이웃으로 가진다. 따라서 1번 수조에는 왼쪽 이웃이 없고, N번 수조에는 오른쪽 이웃이 없다. 수조가 하나뿐이면 이웃은 없다. 서로 떨어진 수조 사이로 물고기를 직접 옮길 수는 없다. 각 수조는 작업 시작 직전의 물고기 수를 기준으로 보낼 곳을 결정한다. 자신의 물고기 수보다 물고기 수가 엄격히 적은 이웃이 없다면 아무 물고기도 보내지 않는다. 그러한 이웃이 하나라면 그 이웃에게 물고기 한 마리를 보낸다. 그러한 이웃이 둘이라면 두 이웃 중 물고기 수가 더 적은 수조에 한 마리를 보낸다. 두 이웃의 물고기 수가 같다면 왼쪽 수조에 보낸다. 한 수조가 보내는 물고기는 최대 한 마리이다. 모든 수조의 결정은 같은 시점의 기록으로 이루어지며, 결정된 이동도 동시에 실행된다. 다른 수조에서 물고기를 받는 수조도 자신의 결정에 따라 물고기를 보낼 수 있다. 다만 이번 작업에서 받은 물고기를 근거로 목적지를 다시 고르거나 추가 이동을 실행하지 않는다. 물고기가 없는 수조는 자신보다 물고기가 적은 이웃을 가질 수 없으므로 물고기를 보내지 않는다. 관리자가 확인하려는 것은 이동 횟수나 이동 경로가 아니라, 작업이 모두 끝난 뒤 각 수조에 남아 있는 물고기 수이다. 주어진 초기 기록에 따라 이동 작업을 한 번 실행한 결과를 수조 번호 순서대로 구한다.

입력

첫째 줄에 정수 N이 주어진다. 1 ≤ N ≤ 100,000이다.
둘째 줄에 정수 A_1, A_2, …, A_N이 공백으로 구분되어 주어진다. 모든 i에 대하여 0 ≤ A_i ≤ 9이다.

출력

이동 작업이 끝난 뒤 1번 수조부터 N번 수조까지의 물고기 수를 한 줄에 공백으로 구분하여 출력한다. 이동이 전혀 발생하지 않으면 초기 물고기 수를 그대로 출력한다.

5
4 1 3 1 4

3 3 2 2 3

1
0

0

4
2 2 1 3

2 1 3 2

출처: Devin.KR 자체 제작