# [COI2021] Cigle

## 题目描述

**译自 [COI 2021](https://hsin.hr/coci/archive/2020_2021/) T2「[Cigle](https://hsin.hr/coci/archive/2020_2021/olympiad_tasks.pdf)」**

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

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

1. 从第 $1$ 行，即最底下一行开始，从左到右放置一些砖块；
2. 在第 $2$ 行，即第 $1$ 行上面一行，从右到左放置一些砖块，使得第 $2$ 行最右边的砖块右边边缘与第 $1$ 行最右边的砖块右边边缘对齐；
3. 在第 $3$ 行，即第 $2$ 行上面一行，从左到右放置一些砖块，使得第 $3$ 行最左边的砖块左边边缘与第 $2$ 行最左边的砖块左边边缘对齐；
4. 在第 $4$ 行，即第 $3$ 行上面一行，从右到左放置一些砖块，使得第 $4$ 行最右边的砖块右边边缘与第 $3$ 行最右边的砖块右边边缘对齐；
5. 以此类推。

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

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

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

## 输入格式

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

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

## 输出格式

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

## 提示

### 样例解释

样例 #3 解释：

![](https://cdn.luogu.com.cn/upload/image_hosting/vx3vf6cp.png)

### 数据范围

对于全部数据，有 $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$ |