问题说明

小玉在玩一维黑白棋游戏。一维黑白棋是一款使用特殊棋子在无限长度的一行格子上进行的游戏。棋子有一个黑面和一个白面，将黑面朝上的棋子翻转后变为白面，将白面朝上的棋子翻转后变为黑面。一维黑白棋的游戏规则如下：

1. 首先，按照顺序放置 $A_1$ 个白棋子，$A_2$ 个黑棋子，$A_3$ 个白棋子，...，$A_N$ 个白棋子。
2. 将一个黑棋子放在任意一个空格上。此时，相邻的两个格子中恰好有一个格子上有一个白棋子。
3. 将放置的黑棋子与最近的另一个黑棋子（这样的棋子总是唯一确定的）之间的所有白棋子翻转为黑棋子。
4. 交换步骤2和步骤3中的黑棋子和白棋子。
5. 重复步骤2到步骤4。
6. 当完成步骤3或步骤4时，如果所有棋子都变成了同一颜色，则游戏结束。

因为翻转太多棋子很麻烦，小玉希望尽量减少翻转次数。请计算在游戏结束之前，小玉所翻转的棋子数量的最小值。

输入

输入以以下格式从标准输入中给出。

$N$ $A_1$ $A_2$ ... $A_N$

• 第一行为一个整数 $N (3 ≦ N < 10^5, N$ 为奇数)。
• 第二行为 $N$ 个整数，以空格分隔，表示棋子的初始配置。其中第 $i (1 ≦ i ≦ N)$ 个数为 $A_i (1 ≦ A_i ≦ 10^8)$。

输出

输出小玉在游戏结束之前所翻转的棋子数量的最小值。输出占一行，末尾包含换行符。

示例1

5
1 2 3 4 5

示例输出1

20

按照下图的方式放置棋子，总共需要翻转 $1+4+5+10 = 20$ 次。

示例2

9
100000000 20 15 11 14 20 15 11 15

示例输出2

554