Data compression
Nurbakyt started getting tired at his developer job and decided that he needs a hobby. Computer games are too brutal and embroidery is too expensive. He started producing music, but everything sounded like "Darude - Sandstorm".
After weeks of struggles, he finally found something he could stick to. Nurbakyt started participating in algorithmic trading tournaments. He uses machine learning to build predictive models.
Usually, Nurba’s dataset looks like an array of n number. Array is too large to execute any deep learning algorithm. Nurbakyt decided that he needs to compress his array of number. While browsing the forums, he found a compression algorithm known as "nonsensical compression". Algorithm splits an array into several segments and replaces the segment with a pair of two highest numbers in the segment. User named ElonMusk228 suggests that the statistical error in compression depends on the sum of these two numbers for each segment. Nurbakyt wants to test this "nonsensical compression" algorithm, so he needs a program that splits the array minimizing the sum of products of two largest numbers in each segment.
Note that to compress an array each segment should contain at least two number.
Input
The first line contains one integer n (2 ≤ n ≤ 10^6).
Second line contains n numbers a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 10^6) - the Nurbakyt’s array.
Output
Print one integer – minimum sum of products of pairs after compression.