题目描述

译自 COI 2021 T2「Cigle」

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

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

• 首先，从第 $1$ 行，即最底下一行开始，从左到右放置一些砖块。
• 紧接着，在第 $2$ 行，即第 $1$ 行上面一行从右到左放置一些砖块，使得中间一行最右边的砖块与最底下一行最右边的砖块右边边缘对齐。
• 然后，在第 $3$ 行从左到右放置剩下所有的砖块，使得中间一行最左边的砖块与最上面一行最左边的砖块左边边缘对齐。
• 以此类推。

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

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

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

输入格式

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

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

输出格式

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

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

提示

【样例解释】

样例 #3 解释：

【数据范围】

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