P8388 [COI 2021] Cigle

**Translated from [COI 2021](https://hsin.hr/coci/archive/2020_2021/) T2 “[Cigle](https://hsin.hr/coci/archive/2020_2021/olympiad_tasks.pdf)”.** 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.

The first line contains an integer $N$. The next line contains $N$ integers $d_i$.

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

Sample explanation: Explanation for Sample #3:  Constraints: For all testdata, $1\le N,d_i\le 5\times 10^3$. | Subtask | Constraint | Score | | :-----: | :--------------------: | :---: | | $1$ | $N\le 20$ | $9$ | | $2$ | $N\le 80$ | $11$ | | $3$ | $N\le 500$，$d_i\le 2$ | $13$ | | $4$ | $N\le 500$ | $15$ | | $5$ | No special constraint | $52$ | Translated by ChatGPT 5