Vidur is very much interested in Job scheduling techniques being used for improving the performance of computing systems. This semester he has been working on developing some new methods to schedule jobs on a computer.
Today, he is testing job scheduling using Dequeues on his system. The jobs which need to be processed by CPU are stored in a Dequeue. Each job is assigned some priority value P. Every time scheduler selects a job from either end of the Dequeue.

Now to counter the problem of Aging, he uses a method different from the existing ones. If the scheduler has to select a job, the priority value of a job becomes P * a, where a is the age of that job.

To analyse the data later, Vidur saves the sum of priorities of each job in a file.

Now, the scheduler works like this. It selects the jobs in such a way that the sum of priorities of the jobs is maximized.

Note:
Priorities are considered just when a job is processed.
The first job has age a = 1. Each job takes one unit of time to get processed. Thus, the age of second job would be a=2.

INPUT:
The first line of input contains N which represents the number of jobs to be processed. Then N lines follow. ith line contains the priority value of ith process.

OUTOUT:
Output the sum for each set of jobs in a single line.

Constraints:
1 < N <=2000
1<=P[i]<=2000