둘이 앉을 수 있는 자리

문제

작은 영화관에는 좌석이 한 줄로 놓인 상영실이 있다. 좌석에는 왼쪽부터 1번부터 N번까지 번호가 붙어 있다. 영화관 직원은 두 사람이 나란히 앉을 수 있는 자리가 얼마나 남았는지 안내판에 표시하려고 한다. 이를 위해 각 좌석이 비어 있는지, 이미 예약되어 있는지를 나타내는 목록을 확인한다. 목록에서 0은 비어 있는 좌석을 뜻하고, 1은 이미 예약된 좌석을 뜻한다. 두 사람이 나란히 앉으려면 번호가 연속한 두 좌석이 모두 비어 있어야 한다. 따라서 i번 좌석과 i+1번 좌석이 모두 0이면 하나의 좌석 쌍으로 센다. 이때 i는 1 이상 N-1 이하인 정수다. 첫 번째 좌석과 마지막 좌석은 번호가 이어지지 않으므로 서로 이웃한 것으로 보지 않는다. 직원이 구하려는 값은 동시에 받을 수 있는 두 사람 손님 일행의 수가 아니라, 손님에게 제시할 수 있는 서로 다른 좌석 쌍의 수다. 따라서 하나의 빈 좌석이 여러 좌석 쌍에 포함되어도 된다. 예를 들어 연속한 빈 좌석이 세 개 있다면 왼쪽 두 좌석을 고르는 방법과 오른쪽 두 좌석을 고르는 방법을 각각 센다. 두 방법이 가운데 좌석을 함께 사용하더라도 서로 다른 선택이기 때문이다. 좌석 쌍은 왼쪽 좌석의 번호가 다르면 서로 다른 것으로 구분한다. 같은 두 좌석에 대해 두 사람이 앉는 순서를 바꾸는 것은 새로운 선택으로 세지 않는다. 목록을 확인하는 동안 예약 상태는 변하지 않으며, 실제로 좌석을 선택하거나 예약 처리할 필요는 없다. 좌석이 하나뿐이거나 조건을 만족하는 두 좌석이 없다면 가능한 좌석 쌍의 수는 0이다. 주어진 목록을 이용하여 안내판에 표시할 좌석 쌍의 수를 구한다.

입력

첫째 줄에 좌석 수를 나타내는 정수 N이 주어진다. 1 ≤ N ≤ 1,000이다.
둘째 줄에 왼쪽 좌석부터 차례대로 예약 상태를 나타내는 정수 N개가 공백으로 구분되어 주어진다. 각 정수는 0 또는 1이다.

출력

번호가 연속하고 모두 비어 있는 좌석 쌍의 수를 정수 하나로 출력한다. 조건을 만족하는 좌석 쌍이 없으면 0을 출력한다.

7
0 0 1 0 0 0 1

3

1
0

0

5
0 0 0 0 0

4

출처: Devin.KR 자체 제작