시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB0000.000%

문제

In a quest to be the very best, Pichuu the electric mouse has since started a new business that better caters to his strengths: using his favorite move Discharge to charge his customers’ phones. A super effective business, it enjoys the patronage of many customers daily.

On a particular day, Pichuu has N customers queuing in wait to charge their phones. He is able to charge multiple phones simultaneously, where the power provided to each phone is equal and constant. Of course, different phone models possess different battery capacities, thus requiring varying lengths of time to charge fully. More specifically, the ith phone takes Ti minutes to become fully charged.

When discharging, Pichuu does not stop until all the phones are fully charged. As such, to avoid getting shocked, customers are forced to wait until the last phone has finished charging before they retrieve their phones. However not all hope is lost: to minimise the total amount of time his customers spend waiting, Pichuu can divide them into an arbitrary amount of contiguous groups, before charging the groups in order. Thus, each group has to wait for the groups in front of them to finish before Pichuu can begin charging their phones.

Every customer will belong to exactly one group, where the ith customer is assigned to the Gth i group. Let the maximum Ti in the kth group be Mk. Hence, the total amount of time spent waiting by the ith customer, Wi, would be the sum of time taken for each group before him as well as his own group. (For an illustration, refer to explanation for sample testcases)

\[W_i = \sum_{n=1}^{G_i}{M_n}\]

To maximise customer satisfaction, Pichuu would like to minimise the sum of the waiting times.

Pichuu has but a mouse-sized brain that is incapable of calculating the optimal way to group his customers. Therefore, he requires your help to find the optimal grouping and hence the minimum sum of waiting time.

입력

Your program must read from standard input.

The first line contains an integer N, the number of customers.

The second line contains N integers, where the ith integer represents the time taken to charge the ith customer’s phone Ti.

출력

Your program must print to standard output.

The output should contain a single integer on a single line, the minimum possible total waiting time.

제한

  • 1 ≤ N ≤ 106
  • 1 ≤ Ti ≤ 109

예제 입력 1

5
1 3 2 6 3

예제 출력 1

27

It is optimal to split the customers into two contiguous groups of (1, 3, 2) and (6, 3). The time taken for the two groups are 3 and 6 respectively as they are the maximum Ti in the groups. The waiting time for the first group is 3 per customer while the waiting time for the second group is 3 + 6 = 9 per customers as the second group has to wait for the first group to finish. Thus the total waiting time is 3 + 3 + 3 + 9 + 9 = 27.

예제 입력 2

7
1 1 2 2 2 2 2

예제 출력 2

14

The optimal grouping is to simply have all the customers in one group and charge their phones all at once. Thus the time taken for this group would be 2. The total waiting time would then be 2 + 2 + 2 + 2 + 2 + 2 + 2 = 14.