Dr. Jackson, a researcher, wishes to perform an experiment. He has a variety of toxic chemicals. Each chemical has some vapor rate. When two chemicals are mixed, then the vapor rate of the mixture is the multiplication of their respective vapor rates.
Dr. Jackson picks two equal-sized sets of non-overlapping,consecutively placed chemicals from a series of chemicals in his lab.He reverses the positions of the chemicals in th set. He then mixes each chemicals from the set. He then mixes each chemical from the first set with the correspondin-placed chemicals of second set.The total vapor rate at the end of the experiment is the sum of the products of respective vapor rates of the chemicals that he mixed from both sets .If the total vapor rate is negatie, he will not pick any set.
Write an alogoritm to find the maximum vapor rate obtained after the experiment.

Input
first line is number N ,chemicals in series ,The second line consists of N space seprated integers.
Output
print an integer representing the maximum vapor rate after the experiment.
Constraints
2<=num<=3000
0<=2*S<=num,where S is the size of the set
-10^6<=vaporRate<=10^6
0<=i<num
example
6
8 0 5 3 9 6
output-72