在平行宇宙 Earth 616 中，年轻的 Stjepan 过着完全不同的生活。目前，他正在艺术设计学院学习砖块工艺课程。像那里的每个孩子一样，他痴迷于图案。例如，他的家庭作业要求他使用 $N$ 块砖建造一面砖墙。但他只有在对二维草图感到满意后才会开始建造。

在草图上，每块砖都可以表示为一个高度为单位长度、宽度为 $d_i$ 的矩形。他预先选定砖块的顺序，并从最底层开始绘制。

在第一行，他将从左到右放置若干块砖。在第二行，他将从右到左放置砖块，第二行的第一块砖将与第一行的最后一块砖对齐（它们的右边缘对齐）。接下来，在第三行，他将再次从左到右放置砖块。第三行的第一块砖将与第二行的最后一块砖对齐，但这次是左边缘对齐。他继续这个过程，直到没有剩余的砖块。他可以选择建造任意行数的墙。

Stjepan 使用超级水泥，因此砖块可以放置在墙上，即使其下方没有其他砖块支撑。墙的“美观度”是指 4 块砖相互接触的位置数量。

对于给定的砖块顺序及其各自的尺寸，请帮助找出墙可能达到的最大美观度。

输入格式

第一行包含一个整数 $N$。 第二行包含 $N$ 个整数 $d_i$。

输出格式

输出可以建造的墙的最大美观度。

子任务

设 $M$ 为最宽砖块的宽度。除非另有说明，否则 $1 \le M \le 5\,000$。

样例

样例输入 1

6
2 2 2 1 1 2

样例输出 1

2

样例输入 2

13
9 5 2 8 8 2 5 9 9 7 8 5 10

样例输出 2

5

样例输入 3

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

样例输出 3

4

说明

第三个样例中美观度为 4 的墙。