Problem Description

Translated from COI 2021 T2 “Cigle”.

In another reality, Earth 616, the young Stjepan lives a completely different life. He is currently studying a bricklaying course at the Academy of Arts and Design. Like every kid there, he is fascinated by patterns.

For example, his assignment requires him to build a wall using $N$ bricks. But before he starts building, he must first complete a 2D sketch and be satisfied with it.

In the sketch, each brick can be represented as a rectangle of height $1$ and width $d_i$. He will determine the order of the bricks in advance and start drawing from the bottom row.

• In the first row, he places some bricks from left to right.
• In the second row, he places bricks from right to left, and the first brick of the second row is aligned to the right edge of the last brick of the first row (i.e., their right edges coincide).
• In the third row, he places bricks from left to right, and the first brick of this row is aligned to the left edge of the last brick of the second row (i.e., their left edges coincide).
• He keeps repeating this process until all bricks are used up. He may freely decide the number of rows of the wall.

Since Stjepan uses a kind of super cement, bricks may be placed even if there is no brick directly supporting them from below.

The “beauty” of the wall is defined as the number of positions where exactly $4$ bricks touch each other.

Given the order of the bricks and their widths, compute the maximum possible beauty of a wall that can be built.

Input Format

The first line contains an integer $N$.

The next line contains $N$ integers $d_i$.

Output Format

Output one integer in a single line, the maximum beauty.

6
2 2 2 1 1 2

2

13
9 5 2 8 8 2 5 9 9 7 8 5 10

5

12
5 5 2 3 2 1 1 5 5 2 5 1

4

Hint

Sample explanation:

Explanation for Sample #3:

Constraints:

For all testdata, $1\le N,d_i\le 5\times 10^3$.

Translated by ChatGPT 5