2021 KBTU Open, Spring Kazakhstan, Alma-Ata, May 30

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.


The first line contains one integer n (2n106).

Second line contains n numbers a1, a2, ..., an (1 ≤ ai106) - the Nurbakyt’s array.


Print one integer – minimum sum of products of pairs after compression.

Time limit 1 second
Memory limit 256 MiB
Input example #1
8 2 10 1
Output example #1
Input example #2
1 2 4
Output example #2
Source 2021 KBTU Open, Spring Kazakhstan, Alma-Ata, May 30, Problem F