Disaster Recovery
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.
xxxxxxxxxx
with Ada.Text_IO, Ada.Integer_Text_IO;
use Ada;
procedure Solution is
-- Enter your code here. Read input from STDIN. Print output to STDOUT
end Solution