Submissions will no longer be placed on the leaderboard. You may still attempt this problem for practice.

Mimmy is managing company X's datacenters. So it is most unfortunate that a power outage took down one of their datacenters. Mimmy called the power supply company and it turns out the outage will not be fixed in the near future. Typically companies have disaster recovery set up for such cases but company X wanted to cut the extra costs. So Mimmy will have to move all the servers from the datacenter to a backup datacenter by hand.

The servers in the datacenter are ordered in line. Mimmy can move either the first or the last server in the line but she can't reach any other server. In one hour Mimmy comes, takes one server to the backup datacenter, sets it up and starts it. Thus every hour Mimmy will "rescue" either the first or the last of the remaining servers. Each server si has an associated downtime cost di - the amount of money that company X will lose every hour that si is down.

Mimmy wants to minimize the costs for company X. She knows all the downtime costs of the servers in the datacenter and she wants to device an optimal way to move them. Help her by writing a program that will find the minimal loss for company X.

Input Format

The first line of the input contains a single integer N(1 <= N <= 1000) - the number of servers in the datacenter Mimmy has to recover. The next line contains N integer numbers di(1 <= di <= 100000)- the downtime costs of the servers in the same order that the servers are placed in the line. The downtime costs are separated by a single space.

Output Format

Output a single number - the minimal loss for company X, for which Mimmy can move all the servers.

Sample Input

4
5 1 4 3

Sample Output

27

Explanation

In the first hour Mimmy will save s1(downtime cost 5), in the second hour she will save s4(d4=3), then she will save the s3(d3=4) and lastly she will save s2(d2=1). The overall cost for the company will be 5 * 1 + 3 * 2 + 4 * 3 + 1 * 4 = 27.

Line: 1 Col: 1
  1. Challenge Walkthrough
    Let's walk through this sample challenge and explore the features of the code editor.1 of 6
  2. Review the problem statement
    Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
  3. Choose a language
    Select the language you wish to use to solve this challenge.3 of 6
  4. Enter your code
    Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
  5. Test your code
    You can compile your code and test it for errors and accuracy before submitting.5 of 6
  6. Submit to see results
    When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
  1. Check your score