일루미네이션 2 (Illumination 2)

JOI 고등학교 학생인 아오이는 문화제에서 복도에 전구 장식을 하기로 했다.

전구 장식은 N개의 전구를 동서 방향으로 한 줄로 늘어놓아 만든다. 전구에는 서쪽부터 차례로 1부터 N까지 번호가 붙어 있다. 각 전구에는 켜짐과 꺼짐의 2가지 상태가 있으며, 처음에는 모든 전구가 꺼져 있다.

아오이가 목표로 하는 전구 장식의 모양은 수열 A1, A2, ..., AN으로 표현되며, Ai = 1일 때는 전구 i를 켜고, Ai = 0일 때는 끄고 싶어 한다. 아오이는 가능한 한 짧은 시간에 이 모양으로 만들려고 한다.

아오이는 처음에 다음 조작을 1회만 할 수 있지만, 하지 않아도 된다.

• 서쪽 끝부터 연속된 구간의 전구를 켠다. 즉, 1 이상 N 이하의 정수 r을 하나 골라 전구 1, 2, ..., r을 켠다.

이 조작에 걸리는 시간은 무시할 수 있다.

그 후, 다음 조작을 몇 번이든 할 수 있다.

• 전구를 하나 골라 그 전구의 상태를 바꾼다 (켜져 있으면 끄고, 꺼져 있으면 켠다).

이 조작에는 1회당 1분이 걸린다.

전구의 개수와 목표로 하는 전구 장식의 모양이 주어질 때, 아오이가 목표 모양으로 만드는 데 최단으로 몇 분이 걸리는지 구하는 프로그램을 작성하시오.

입력은 다음 형식으로 표준 입력에서 주어진다.

N
A1 A2 … AN

표준 출력에, 목표 모양으로 만드는 데 최단으로 몇 분이 걸리는지 1행으로 출력하시오.

• 1 ≦ N ≦ 200 000.
• Ai는 0 또는 1이다 (1 ≦ i ≦ N).
• 입력되는 값은 모두 정수이다.