题目描述

译自 COI $2021$ T$2$「Cigle」

您是一位设计师，现在您正在思考您的下一个设计是什么。

您可以使用 $N$ 块分别长为 $d_i$ 宽为一个单位长度的砖来建造一个多行的砖墙，行数可以任意选择，每行长一个单位长度，具体方式是：

1. 从第 $1$ 行，即最底下一行开始，从左到右放置一些砖块。

2. 紧接着，在第 $2$ 行，即第 $1$ 行上面一行从右到左放置一些砖块，使得第 $2$ 行最右边的砖块与最底下一行最右边的砖块右边边缘对齐。

3. 然后，在第 $3$ 行，即第 $2$ 行上面一行从左到右放置一些砖块，使得第 $3$ 行最左边的砖块与第 $2$ 行最左边的砖块左边边缘对齐。

4. 以此类推，直到砖块放完为止。

由于砖是神奇的，所以砖可以浮空。

对于一座砖墙，他的美丽度被定义为被四个砖块共顶点的顶点个数。

按砖块的放置顺序给定每块砖的长度，求出最大美丽度。

输入格式

第一行为一个整数 $N$。

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

输出格式

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

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

4

数据规模与约定

对于全部数据，有 $1 \le N, d_i \le 5 \times 10^3$。