题目描述

译自 COI 2021 T2「Cigle」

在另一个现实中的 Earth 616，年轻的 Stjepan 过着完全不同的生活。目前他在艺术与设计学院学习一门砌砖课程。像那里的每个孩子一样，他对图案十分着迷。

例如，他的作业要求他用 $N$ 块砖建造一面墙。但在开始建造之前，他必须先完成一个二维草图并对其满意。

在草图中，每块砖可以表示为一个高度为 $1$、宽度为 $d_i$ 的矩形。他会事先确定砖块的顺序，并从最底下一行开始绘制。

• 在第一行，他从左到右放置若干砖块。
• 在第二行，他从右到左放置砖块，并且第二行的第一块砖与第一行的最后一块砖右边对齐（即右边缘对齐）。
• 在第三行，他从左到右放置砖块，这一行的第一块砖与第二行的最后一块砖左边对齐（即左边缘对齐）。
• 他不断重复这个过程，直到所有砖块都用完。他可以自由决定墙的行数。

由于 Stjepan 使用了一种超级水泥，因此砖块可以放置在没有其他砖块直接支撑的位置。

墙的“美观度”被定义为：有多少个位置上恰好有 $4$ 块砖相互接触。

给定砖块的顺序及其宽度，请你计算可以建造出的墙的最大美观度。

输入格式

第一行为一个整数 $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$。

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$