문제

흰색과 검은색 바둑돌을 테이블 위에 늘어놓으며 논다. 먼저 테이블의 왼쪽 끝에 바둑돌을 놓는다. 다음으로 왼쪽에서 $2$번째 자리에 바둑돌을 놓는다. 이를 $n$번 반복하여 $n$개의 바둑돌을 가로로 한 줄로 늘어놓는다. 단, 새로 $i$번째 바둑돌을 놓을 때에는 다음 규칙에 따라 테이블 위의 바둑돌을 바꾼다.

• $i$가 홀수인 경우: 테이블에 놓여 있던 바둑돌은 바꾸지 않고, 새로운 바둑돌을 왼쪽에서 $i$번째에 놓는다.
• $i$가 짝수인 경우: 새로 왼쪽에서 $i$번째에 놓는 바둑돌의 색과 테이블 위의 오른쪽 끝 바둑돌의 색이 같은 경우에는 테이블 위의 바둑돌은 바꾸지 않고 새로운 바둑돌을 왼쪽에서 $i$번째에 놓는다. 그렇지 않은 경우, 즉 새로 왼쪽에서 $i$번째에 놓는 바둑돌의 색과 테이블 위의 오른쪽 끝 바둑돌의 색이 다른 경우에는 먼저 테이블 위의 오른쪽 끝에 연속된 같은 색의 바둑돌을 모두 제거하고 $i$번째 바둑돌과 같은 색의 바둑돌로 바꾼다. 그리고 테이블의 오른쪽 끝에 $i$번째 바둑돌을 놓는다.

예를 들어 처음 $7$개의 바둑돌을 놓은 시점에서,

$$\circ \circ \bullet \bullet \circ \circ \circ$$

와 같이 되어 있었다고 하자 ($\circ$는 흰 바둑돌을, $\bullet$는 검은 바둑돌을 나타낸다).

• $8$번째 바둑돌이 흰색($\circ$)인 경우에는 오른쪽 끝의 바둑돌과 같은 색이므로 그대로 놓는다. 따라서 테이블 위의 바둑돌은 다음과 같이 된다:

$$\circ \circ \bullet \bullet \circ \circ \circ \circ$$

• $8$번째 바둑돌이 검은색($\bullet$)인 경우에는 오른쪽 끝의 바둑돌($\circ$)과 색이 다르므로 먼저 테이블의 오른쪽 끝에 있는 $3$개의 연속된 흰 바둑돌($\circ$)을 제거하고 검은 바둑돌($\bullet$)로 바꾼다. 그리고 오른쪽 끝에 $8$번째 바둑돌을 놓는다. 따라서 테이블 위의 바둑돌은 다음과 같이 된다:

$$\circ \circ \bullet \bullet \bullet \bullet \bullet \bullet$$

입력으로 놓을 바둑돌의 순서가 주어졌을 때, $n$개의 바둑돌을 모두 늘어놓은 후 테이블 위에 놓여 있는 흰 바둑돌의 개수를 구하는 프로그램을 작성하라.

입력

$1$번째 줄에는 양의 정수 $n$ ($1 \le n \le 100\,000$)이 적혀 있다. $2$번째 줄 이후의 제 $i+1$번째 줄 ($1 \le i \le n$)에는 $i$번째에 놓는 바둑돌의 색을 나타내는 정수 $c_{i}$가 적혀 있으며, $c_{i}$가 $0$이면 $i$번째에 놓는 바둑돌의 색이 흰색임을, $1$이면 $i$번째에 놓는 바둑돌의 색이 검은색임을 나타낸다.

채점용 데이터 중 배점의 $50\%$에 대해서는 $n \le 10\,000$을 만족한다.

출력

$n$개의 바둑돌을 모두 늘어놓은 후에 테이블 위에 놓여 있는 흰 바둑돌의 개수만을 포함하는 $1$줄을 출력하라.

입출력 예제

입력 예제 1

8
1
0
1
1
0
0
0
0

출력 예제 1

6

입력 예제 2

8
1
0
1
1
0
0
0
1

출력 예제 2

2