← 返回题目列表

AtCoder · cf_2015_morning_hard_a

C. 一维奥赛罗

中文机器翻译题面 查看原题

問題文

林戈正在扮演一维奥赛罗。一维奥赛罗无限长 1 这是一种使用排成一排的方块和特殊棋子进行的游戏。一维黑白棋中使用的棋子正面为黑色,背面为白色;当黑色棋子翻转时,它会变成白色棋子;当白色棋子翻转时,它会变成黑色棋子。一维奥赛罗的进展如下。

  1. 一、白片 A_1 件,黑色件 A_2 件,白色件 A_3 碎片,...,白色碎片 按此顺序将 A_N 块放入连续的方格中。
  2. 在任意空方格上放置一个黑色棋子。这时,邻居 2 刚出方块 1 方格内必须有一块白色棋子。
  3. 2. 将你所放置的黑子与最接近的黑子(此类子总是唯一的)之间的所有白子翻转为黑子。 执行交换
  4. 2. 和 3. 的黑色和白色的操作。 重复
  5. 2. 〜 4. 。
  6. 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 你将把棋子翻转过来。

figure1

入力例2

9
100000000 20 15 11 14 20 15 11 15

出力例2

554