Minimize Total Charging Waiting Time

Pichuu has N customers waiting for their phones to be charged. Each phone is charged with the same constant power, but different phone models have different battery capacities. Thus, the i-th phone requires T_i minutes to fully charge.

Pichuu will not stop charging until all phones are fully charged. To avoid making customers wait too long, Pichuu can partition the customers into several consecutive groups and charge them group by group. The customers in a group must wait until all the previous groups have been completely charged.

For the k-th group, the charging time is determined by the maximum charging time in that group, denoted as M_k. Thus, the total waiting time of the i-th customer (who belongs to group G_i) is given by:

Your task is to help Pichuu minimize the total waiting time by choosing an optimal grouping strategy. In other words, partition the list of T_i (in their given order) into consecutive groups such that the total waiting time, defined as the sum of the waiting times of all customers, is minimized.

Note: For a segment covering customers from index j+1 to i (1-indexed), the cost contributed by this group is (i - j) \times \max(T_j+1, \ldots, T_i). You may use dynamic programming to solve this problem.

inputFormat

The first line contains a single integer N, the number of customers. The second line contains N space-separated integers T1, T2, ..., TN, where Ti represents the time (in minutes) required to fully charge the i-th phone.

outputFormat

Output a single integer, the minimum total waiting time if the customers are grouped optimally.

sample

3
3 2 1

7