問題文
林戈正在扮演一维奥赛罗。一维奥赛罗无限长 1 这是一种使用排成一排的方块和特殊棋子进行的游戏。一维黑白棋中使用的棋子正面为黑色,背面为白色;当黑色棋子翻转时,它会变成白色棋子;当白色棋子翻转时,它会变成黑色棋子。一维奥赛罗的进展如下。
- 一、白片 A_1 件,黑色件 A_2 件,白色件 A_3 碎片,...,白色碎片 按此顺序将 A_N 块放入连续的方格中。
- 在任意空方格上放置一个黑色棋子。这时,邻居 2 刚出方块 1 方格内必须有一块白色棋子。
- 2. 将你所放置的黑子与最接近的黑子(此类子总是唯一的)之间的所有白子翻转为黑子。 执行交换
- 2. 和 3. 的黑色和白色的操作。 重复
- 2. 〜 4. 。
- 3. 或 如果 4. 完成时所有棋子颜色相同,则游戏此时结束。
由于翻转很多棋子很困难,林戈想减少翻转棋子的次数。求游戏结束前林戈翻开的棋子数量的最小和。
入力
输入是按以下格式从标准输入给出的。
N A_1 A_2 ... A_N
- 1 行包含一个整数 N (3 ≦ N < 10^5, N は奇数) 。
- 2 行表示有关片段初始排列的信息。 N 整数由空格分隔。其中 i (1 ≦ i ≦ N) 第 A_i (1 ≦ A_i ≦ 10^8) 。
出力
求林戈在游戏结束前翻转棋子数量的最小总和。 在 1 行上输出。在输出末尾插入换行符。
入力例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