日本情報オリンピック 第1回 女性部門

2021年4月27日
情報オリンピック日本委員会

問題文

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