피자 데이 (Pizza Day)

정올이는 성공한 피자가게의 사장이다. (블루리본을 10개나 받았다)

오늘은 정올이가 가게를 오픈한지 10년이 되는 기념일로, 이 날을 기념하기 위해 특별한 이벤트를 열었다.

이벤트의 이름은 피자 데이(Pizza Day)!

피자 데이는 N명의 학생들을 초대하여 그들이 원하는 만큼 피자를 원없이 먹게해주는 날이다.

첫 번째 학생은 A_1 개의 조각의 피자를 먹고 싶어하고, i번째 학생은 A_i 개의 조각의 피자를 먹고 싶어한다.

정올이는 1분에 한 조각의 피자를 만들어 학생에게 준다.

각 학생들은 1번부터 N번까지 순서대로 줄을 서서 피자를 한 조각씩 받아먹는데, 피자를 더 먹고 싶다면 다시 맨 뒤로 가서 줄을 서야한다.

이 때, 각 학생들이 원하는 피자를 먹기 위해 각각 얼마나 기다려야 하는지 알아보자.

입력

첫 줄에 학생의 수 N이 주어진다. (1 \le N \le 1,000)

두 번째 줄에 A_1, A_2, ..., A_N이 주어진다. (1 \le A_i \le 100, 1 \le i \le N)

출력

첫 줄에 공백으로 구분하여 각 학생들이 기다려야 하는 시간(분)을 출력한다.

부분문제

번호	점수	조건
#1	50점	N \le 10
#2	50점	추가 제한 없음

예제

1분: 줄에 맨 앞에 서있던 1번 사람이 피자 한 조각을 먹고 만족한다.

2분: 2번 사람이 피자 한 조각을 먹고 다시 줄의 맨 뒤로 가서 선다.

3분: 3번 사람이 피자 한 조각을 먹고 만족한다.

4분: 4번 사람이 피자 한 조각을 먹고 다시 줄의 맨 뒤로 가서 선다.

5분: 2번 사람이 피자 한 조각을 먹고 다시 줄의 맨 뒤로 가서 선다.

6분: 4번 사람이 피자 한 조각을 먹고 다시 줄의 맨 뒤로 가서 선다.

7분: 2번 사람이 피자 한 조각을 먹고 만족한다.

8분: 4번 사람이 피자 한 조각을 먹고 다시 줄의 맨 뒤로 가서 선다.

9분: 4번 사람이 피자 한 조각을 먹고 만족한다.

태그

출처

2017 AIPO Preliminary Round 4번

피자 데이 (Pizza Day) 1s 1024MB