P8388 [COI 2021] Cigle

**译自 [COI 2021](https://hsin.hr/coci/archive/2020_2021/) T2「[Cigle](https://hsin.hr/coci/archive/2020_2021/olympiad_tasks.pdf)」** 在另一个现实中的 Earth 616，年轻的 Stjepan 过着完全不同的生活。目前他在艺术与设计学院学习一门砌砖课程。像那里的每个孩子一样，他对图案十分着迷。 例如，他的作业要求他用 $N$ 块砖建造一面墙。但在开始建造之前，他必须先完成一个二维草图并对其满意。 在草图中，每块砖可以表示为一个高度为 $1$、宽度为 $d_i$ 的矩形。他会事先确定砖块的顺序，并从最底下一行开始绘制。 * 在第一行，他从左到右放置若干砖块。 * 在第二行，他从右到左放置砖块，并且第二行的第一块砖与第一行的最后一块砖右边对齐（即右边缘对齐）。 * 在第三行，他从左到右放置砖块，这一行的第一块砖与第二行的最后一块砖左边对齐（即左边缘对齐）。 * 他不断重复这个过程，直到所有砖块都用完。他可以自由决定墙的行数。 由于 Stjepan 使用了一种超级水泥，因此砖块可以放置在没有其他砖块直接支撑的位置。 墙的“美观度”被定义为：有多少个位置上**恰好有 $4$ 块砖相互接触**。 给定砖块的顺序及其宽度，请你计算可以建造出的墙的最大美观度。

第一行为一个整数 $N$。 接下来一行 $N$ 个整数 $d_i$。

输出一行一个整数，表示最大美丽度。

【样例解释】 样例 #3 解释：  【数据范围】 对于全部数据，有 $1\le N,d_i\le 5\times 10^3$。 | Subtask | 限制 | 分数 | | :-----: | :--------------------: | :--: | | $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$ | 无特殊限制 | $52$ |