Skyline

You want your city to have a good skyline. You will build $N$ skyscrapers in a straight row, and the $i$-th of them must end up with exactly $h_i$ floors.

Three construction companies made you different offers. The first one builds one floor on any single skyscraper for 3 million euros. The second one picks two neighbouring skyscrapers and builds one floor on each of them, two floors in total, for 5 million euros. The two floors do not have to be at the same height. The third one picks three consecutive skyscrapers and builds one floor on each of them, three floors in total, for 7 million euros.

You can order the work in any way you want. Find the smallest total amount of money that finishes the construction.

The first line contains the number of skyscrapers $N$. ($1 \le N \le 300$)

The second line contains $h_1, h_2, \dots, h_N$ separated by spaces. ($1 \le h_i \le 200$)

Print the minimum cost as one integer, in millions of euros.