Maximum happiness

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Everyone celebrates the holiday of the 47th day of the year in their own way. Some meet with their friends and throw a loud party. Some set off loud fireworks. Some sit and solve holiday problems.

Mr. Dmytro decided to enjoy a special holiday set of candies on the occasion of the holiday. The set consists of \(n\) candies. Each candy has its own happiness level — an integer 4 or 7. All candies are arranged in a row, so that each candy except the first and the last has exactly two neighbors.

The feature of this set is that by eating a certain candy, the eater’s happiness level increases by the total happiness level of the two neighbors of the candy they eat. Note that eating the first or the last candy from the set is prohibited.

Mr. Dmytro wants to eat all the candies except the first and the last in order to achieve maximum happiness. Help him determine the maximum level of happiness he can achieve.

Input

The first line contains a single integer \(n\) — the number of candies in the set.

The second line contains \(n\) integers \(a_i\) — the happiness levels of the candies in the order they are arranged in the set.

Output

In a single line, print one integer — the maximum happiness level that can be achieved.

Constraints

7 tests: \(3 \le n \le 20\),

15 tests: \(3 \le n \le 100\),

25 tests: \(3 \le n \le 10^5\),

\(a_i \in \{4, 7\}\).

Samples