카페의 순환 추출대

문제

한 카페에서는 여러 잔의 음료를 번갈아 만드는 순환 추출대를 사용한다. 영업을 시작하기 전에 주문 N개가 한꺼번에 접수되었고, 주문마다 필요한 추출 횟수가 정해져 있다. 주문에는 접수 순서대로 1번부터 N번까지 번호를 붙인다. 모든 주문은 시각 0에 준비되어 있으며, 처리하는 동안 새로운 주문은 들어오지 않는다. 추출대 앞에는 주문을 담아 두는 대기 줄이 있다. 처음에는 1번 주문이 맨 앞에 있고, 그 뒤로 2번부터 N번까지 번호 순서대로 놓여 있다. 추출대는 대기 줄의 맨 앞 주문을 꺼내 그 주문의 추출을 정확히 한 번 진행한다. 추출 한 번에는 정확히 1초가 걸리며, 여러 주문을 동시에 추출할 수는 없다. 한 번의 추출이 끝났을 때 해당 주문에 필요한 추출 횟수를 모두 채웠다면 음료가 완성된다. 완성된 주문은 대기 줄에서 빠지고, 그 순간의 시각을 완성 시각으로 기록한다. 아직 추출이 더 필요하면 그 주문을 대기 줄의 맨 뒤로 보낸다. 이후 같은 규칙으로 맨 앞 주문을 처리한다. 주문을 꺼내거나 맨 뒤로 보내는 데에는 시간이 걸리지 않으며, 대기 줄이 비기 전까지 추출대는 쉬지 않는다. 따라서 첫 번째 추출은 시각 0에 시작하여 시각 1에 끝나고, 두 번째 추출은 시각 2에 끝난다. 대기 중인 주문이 하나뿐이어도 한 번 추출할 때마다 같은 규칙을 적용한다. 필요한 추출 횟수가 적은 주문이 반드시 먼저 완성되는 것은 아니며, 대기 줄에서 어느 순서로 처리되는지도 완성 시각에 영향을 준다. 카페는 완성된 순서와 별개로 접수 번호에 맞추어 손님에게 예상 기록을 전달하려 한다. 모든 주문이 완성될 때까지 추출대를 작동시켰을 때, 각 주문의 완성 시각을 원래 주문 번호 순서대로 구해야 한다.

입력

첫째 줄에 주문의 개수 N이 주어진다. N은 1 이상 20,000 이하의 정수다.
둘째 줄에 각 주문에 필요한 추출 횟수 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다. 모든 A_i는 1 이상 9 이하의 정수다.

출력

1번 주문부터 N번 주문까지의 완성 시각을 공백으로 구분하여 한 줄에 출력한다. 각 시각은 시각 0부터 지난 초를 나타내는 정수다.

4
2 1 3 2

5 2 8 7

1
9

9

출처: Devin.KR 자체 제작