在一望无际的湖面上，静静排着一串小岛，共有 $n$ 座，从左到右编号为 $1\sim n$。相邻小岛之间搭着 $n-1$ 座会“耗尽”的临时魔法桥。

每座桥都“脾气有限”：它只允许被通过若干次。一旦累计通过次数用完，这座桥就会瞬间崩塌，永不复原。

某天，徐老师决定展开一场“桥上漫游”的教学探险：

• 他可以任选一个小岛作为起点。
• 此后，他可以沿着尚未崩塌的桥在相邻小岛之间穿行。每跨过一座桥，都会消耗这座桥的可用次数 1 次（无方向区分，往返都算）。
• 一旦他所处的小岛两侧都没有可用次数 $>0$ 的桥，便只能止步于此，探险结束。途中不能中途停在桥上，也不能在桥中折返（必须从桥的这一端走到另一端）。

记徐老师全程跨桥的总次数为他的“成绩”。你的任务是：求出在最优起点与最优行走策略下，徐老师能获得的最高成绩。

输入格式

• 第一行输入整数 $n$ —— 小岛数量。
• 第二行输入 $n-1$ 个整数 $a_i$（$i=1,2,\ldots,n-1$），表示连接小岛 $i$ 与 $i+1$ 的那座桥可被通过的总次数。

输出格式

输出一个整数，表示能达到的最高成绩（即最大跨桥次数）。

样例输入

5
2 1 2 1

样例输出

5

样例说明 若从小岛 $3$ 出发，可依次走到 $4,3,2,1,2$，一共跨桥 5 次，得到成绩 5。此时只剩下 $4$ 与 $5$ 之间的一座未崩塌桥，但徐老师已在小岛 $2$，且他两侧的桥都无法继续使用，探险结束。

数据范围

• 对于 50% 的数据：$2\le n\le 5$，$1\le a_i\le 5$；
• 对于 100% 的数据：$2\le n\le 10^5$，$1\le a_i\le 10^9$。