← 返回题目列表

AtCoder · joi2008ho_a

A. 围棋排列

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

配点: 20 点

通过在桌子上排列白色和黑色的围棋棋子来进行游戏。首先,将围棋棋子放在桌子的左端。 从左往下依次是 将围棋棋子放在第 2 个位置。这个 重复 n 次 将 n 棋子排成水平线。然而,新 当下第 i 颗棋子时,按照以下规则将棋子放回桌上。 如果

  • i 是奇数:桌上的棋子不被替换,新的棋子从左边开始放置。 将其放置在 i 。 如果
  • i 是偶数:从左边新 i 如果要下的围棋子颜色与桌上最右边的围棋子颜色相同,则不更换桌上的围棋子,而是从左边下下新的围棋子。 将其放置在 i 。如果没有,即从左边开始新的 如果 i 所放的围棋子颜色与棋盘右端的棋子颜色不同,则先将棋盘右端所有连续的相同颜色的围棋棋子移走。 替换为与第i 颗棋子颜色相同的棋子。在桌子的右侧 放置第 i 颗棋子。

例如,第一个 当放置 7 围棋棋子时, 假设它变成

\gdef\W{\Large \kern-0.05em\raisebox{-0.05em}{○}\kern-0.05em}\gdef\B{\Large \kern-0.05em\raisebox{-0.05em}{●}\kern-0.05em}\W\W\B\B\W\W\W

。 (\W 是一块白色的围棋棋子,\B 代表黑色围棋棋子。 )

  • 8 第颗围棋子是白色的 (\W),它与最右边的围棋棋子颜色相同,所以按原样放置。因此,桌上的围棋棋子是 \W\W\B\B\W\W\W\W 变为。
  • 8 第颗围棋子是黑色的 (\B),最右边的围棋子(\W)具有不同的颜色,因此首先查看表格的右端。 3 连续白棋棋子 (\W)并移除黑色围棋棋子(\B)。在最右边 放置第 8 颗棋子。因此,桌上的围棋棋子是 \W\W\B\B\B\B\B\B 变为。

给定作为输入放置的围棋棋子的顺序, 排列完n 棋子后,编写一个程序计算桌上白棋子的数量。


入力

输入文件的文件名是 input.txt 。 1 行是正整数 n (1 \leqq n \leqq 100000)被写入。2 行后行 i + 1 行目 (1 \leqq i \leqq n)有 代表第i 颗围棋棋子颜色的整数 写入 c_i , 放置在c_i 是 存在 0 如果 如果对满足 i 处的围棋子颜色是白色。1 如果 如果对满足 i 表示所下围棋的颜色为黑色。

评分数据中,分配的分数 50 对于%, n \leqq 10000 很满意。

出力

输出文件的文件名是 output.txt 。

output.txt 是 仅包括n 棋子排序后放在桌上的白棋子数量。 由 1 行组成。


入力例 1

8
1
0
1
1
0
0
0
0

出力例 1

6

入力例 2

8
1
0
1
1
0
0
0
1

出力例 2

2