Cigle

In an alternate reality Earth 616, young Stjepan lives a totally different life. He is enrolled in a brick-crafting course at the School of Arts and Design. Like every child there, he is obsessed with patterns. For example, his homework requires him to build a brick wall using $N$ bricks. But he will not start building until he is satisfied with his two-dimensional sketch.

On the sketch, every brick is a rectangle with unit height and width $d_i$. He chooses the order of the bricks beforehand and starts sketching from the bottom-most row.

In the first row, he places some number of bricks from left to right. In the second row, he places bricks from right to left, and the first brick in the second row aligns with the last brick in the first row (their right edges align). Next, in the third row, he places bricks again from left to right. The first brick in the third row aligns with the last brick in the second row, but this time by the left edges. He continues this process until no bricks are left. He may build a wall with any number of rows.

Stjepan uses super cement, so a brick may be placed so that no other brick is directly underneath it. Beauty of the wall is the number of places where 4 bricks touch.

For a given order of bricks and their respective sizes, find the largest possible beauty of the wall.

The first line contains the integer $N$ from the problem statement.

The second line contains $N$ integers $d_i$ from the problem statement.

Print the largest possible beauty of any wall that can be built.

Let $M$ be the width of the widest brick. Unless otherwise specified, $1 \le M \le 5000$ holds.

The wall with beauty 4 for the third sample is shown below.