問題
白と黒の碁石をテーブルの上にならべて遊ぶ.まずテーブルの左端に碁石を置く. 次に左から 2 番目の場所に碁石を置く.これを n 回繰り返して n 個の碁石を横一列 にならべる.ただし,新しく i 番目の碁石を置く際には,次のルールに従ってテー ブル上の碁石を置き換える.
- i が奇数の場合: テーブルに置いてあった碁石は置き換えず,新しい碁石を左 から i 番目に置く.
- i が偶数の場合: 新しく左から i 番目に置く碁石の色とテーブル上の右端の碁 石の色が同じ場合は,テーブル上の碁石は置き換えず,新しい碁石を左から i 番目に置く.そうでない場合,すなわち,新しく左から i 番目に置く碁石の色 とテーブル上の右端の碁石の色が異なる場合は,まずテーブル上の右端の連続 した同色の碁石を全て取り除き,i 番目の碁石と同色の碁石に置き換える.そ してテーブルの右端に i 番目の碁石を置く.
例えば,最初の 7 個の碁石を置いた時点で,
○○●●○○○
となっていたとする. (○は白の碁石を,●は黒の碁石を表す. )
- 8 番目の碁石が白(○)の場合は,右端の碁石と同色なので,そのまま置く.し
たがって,テーブル上の碁石は
○○●●○○○○
となる. - 8 番目の碁石が黒(●)の場合は,右端の碁石(○)と色が異なるので,まず
テーブルの右端にある 3 個の連続した白い碁石(○)を取り除き,黒い碁石
(●)に置き換える.そして右端に 8 番目の碁石を置く.したがって,テーブ
ル上の碁石は
○○●●●●●●
となる.
入力として置く碁石の順番が与えられたとき,n 個の碁石をならべ終わった後,テー ブル上に置いてある白い碁石の個数を求めるプログラムを作成せよ.
入力
入力ファイルのファイル名は input.txt である. 1 行目には正整数 n (1 ≤ n ≤ 100000) が書かれている.2 行目以降の第 i + 1 行目 (1 ≤ i ≤ n) には,i 番目に置く碁石の色を表す整数 ci が書かれており,ci が 0 なら i 番目に置く碁石の色が白であることを,1 なら i 番目に置く碁石の色が黒であることを表す.
採点用データのうち, 配点の 50% 分については, n ≤ 10000 を満たす.
出力
出力ファイルのファイル名は output.txt である. output.txt は,n 個の碁石をならべ終わった後にテーブル上に置いてある白い碁 石の個数だけを含む 1 行からなる.
入出力の例
例1
input.txt
8 1 0 1 1 0 0 0 0
output.txt
6
例2
input.txt
8 1 0 1 1 0 0 0 1
output.txt
2