시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB80624573.770%

문제

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

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

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

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

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

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

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

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

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

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

입력

入力は以下の形式で標準入力から与えられる.

N
A1 A2  AN

출력

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

제한

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

서브태스크

번호배점제한
145

N ≦ 2 000

255

追加の制約はない.

예제 입력 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

채점 및 기타 정보

  • 예제는 채점하지 않는다.