004 - イルミネーション 2 (Illumination 2)

問題

JOI 高校の生徒である葵は，文化祭で廊下に電飾を飾ることにした．

電飾は，N 個の電球を東西方向に一列に並べて作る．電球には西側から順に 1 から N までの番号が付けられている．各電球にはオンとオフの 2 つの状態があり，はじめ電球はすべてオフの状態である．

葵が目標とする電飾の模様は数列 A₁, A₂, ..., A_N で表され，A_i = 1 のときは電球 i をオンに，A_i = 0 のときはオフにしたい．葵はできるだけ短い時間でこの模様にしようと考えた．

葵は最初に次の操作を 1 回だけ行うことができるが，行わなくてもよい．

• 西側の端から連続した区間の電球をオンにする．すなわち， 1 以上 N 以下の整数 r を 1 つ選び，電球 1, 2, ... , r をオンにする．

この操作を行うのにかかる時間は無視できる．

その後，次の操作を何回でも行うことができる．

• 電球を 1 つ選び，その電球の状態を変更する (オンならばオフに，オフならばオンにする)．

この操作を行うには 1 回につき 1 分かかる．

電球の個数，目標とする電飾の模様が与えられたとき，葵が目標の模様にするのに最短で何分かかるかを求めるプログラムを作成せよ．

制約

• 1 ≦ N ≦ 200 000．
• A_i は 0 か 1 のいずれかである (1 ≦ i ≦ N)．
• 入力される値はすべて整数である．

小課題

1. (45 点) N ≦ 2 000．
2. (55 点) 追加の制約はない．

入力

入力は以下の形式で標準入力から与えられる．
N
A₁ A₂ … A_N

出力

標準出力に，目標の模様にするのに最短で何分かかるかを 1 行で出力せよ．

入出力例

入力例1

6
0 1 1 0 0 1

出力例1

2

例えば，葵は最初に r = 3 を選び，電球 1, 2, 3 をオンにする．この操作にかかる時間は 0 分である．その後，電球 1 をオンからオフに，電球 6 をオフからオンに状態を変更する．この操作にはそれぞれ 1 分ずつ合計で 2 分かかる．2 分未満で目標の模様にすることはできないので，2 を出力する．

入力例2

4
0 0 0 1

出力例2

1

この入力例では，葵は最初の操作は行わない．その後，電球 4 をオフからオンに状態を変更する．この操作には 1 分かかり，1 分未満で目標の模様にすることはできないので，1 を出力する．

入力例3

4
1 1 1 1

出力例3

0

この入力例では，葵は最初に r = 4 を選び電球 1, 2, 3, 4 をオンにすることで，目標の模様にすることができる．この操作にかかる時間は 0 分であるので，0 を出力する．

入力例4

15
1 0 0 0 0 1 1 1 0 1 0 0 1 0 1

出力例4

6