충전 완료 시각 장부

문제

한 전기차 충전소에는 예약 차량 전용 충전기가 한 대 있다. 오늘 예약된 차량 N대는 모두 영업 시작 전에 도착해 있다. 직원은 각 차량에 필요한 충전 시간을 확인한 뒤, 정해진 규칙에 따라 차량을 한 대씩 연결하려 한다. 차량에는 예약 접수 순서대로 1번부터 N번까지 번호가 붙어 있으며, i번 차량의 충전에는 T_i분이 걸린다. 충전 순서는 필요한 충전 시간이 짧은 차량부터 정한다. 충전 시간이 같은 차량이 여러 대이면 예약 번호가 작은 차량을 먼저 연결한다. 이 순서는 영업을 시작하기 전에 한 번 정하며, 충전 도중에는 바꾸지 않는다. 모든 충전 시간은 양의 정수이고 차량마다 서로 다를 필요는 없다. 영업 시작 시각을 0분으로 정한다. 첫 번째 차량은 0분에 충전을 시작하고, 이후 차량은 바로 앞 차량의 충전이 끝난 시각에 즉시 충전을 시작한다. 차량을 연결하거나 빼는 데 걸리는 시간은 없으며, 한 차량의 충전을 중간에 멈추지도 않는다. 따라서 충전기가 쉬는 시간은 없다. 직원은 각 차량이 충전을 마친 시각을 장부에 적는다. 장부에 적는 값은 해당 차량이 실제로 충전한 시간만이 아니라, 영업 시작부터 그 차량의 충전이 끝날 때까지 흐른 전체 시간이다. 예를 들어 앞 차량의 충전이 3분에 끝나고 다음 차량에 5분이 필요하면, 다음 차량의 완료 시각은 8분이다. 정산을 위해 장부에 적힌 모든 완료 시각의 합이 필요하다. 예약 차량 수와 각 차량의 충전 시간이 주어질 때, 규칙에 따라 충전했을 때의 완료 시각 합을 구하는 프로그램을 작성한다. 마지막 차량의 완료 시각만 출력하는 것이 아니라 차량 N대의 완료 시각을 모두 더한 값을 출력해야 한다.

입력

첫째 줄에 차량 수 N이 주어진다.
둘째 줄에 예약 번호 순서대로 T_1, T_2, ..., T_N이 공백으로 구분되어 주어진다.
모든 입력값은 정수이며, 1 ≤ N ≤ 60,000, 1 ≤ T_i ≤ 999이다.

출력

모든 차량의 충전 완료 시각의 합을 정수 하나로 출력한다. 단위나 다른 문자는 출력하지 않는다.

5
4 2 4 1 3

34

3
7 7 7

42

출처: Devin.KR 자체 제작