You want the skyscrapers in your city to look good. It is decided to build N skyscrapers in a row. The skyscraper with number i must have exactly h[i] floors.
You have offers from various construction companies. The first of them proposes to build one floor in any of the skyscrapers for 3 million euros. The second proposes to build one floor in each of the two neighboring skyscrapers for 5 million euros. Note that it doesn't matter if these floors are at the same height or not. A third company is offering to build one floor in each of three consecutive skyscrapers for 7 million euros.
You can build the floors in any order. Calculate the minimum amount of money required for construction.
Input
The first line contains one integer N (1 ≤ N ≤ 300). The second line contains N integers h[1], h[2] ..., h[N], 1 ≤ h[i]≤ 200.
Imprint
In a single line print one integer: the minimum amount of money for construction, in millions.