Server Corridor

면접 대비

시간 제한1초메모리 제한2048 MB

요약

복도 칸이 비어 있음, 꺼짐, 켜짐으로 주어질 때, 인접한 두 서버가 동시에 켜지지 않도록 추가로 켤 수 있는 서버의 수를 센다.

난이도: 보통10점 중 4점
유형: 그리디, 배열, 문자열
정답자: 아직 제출이 없습니다

문제

Audrey is system administrator for miHoYo! It is her job to manage the server room and keep her favorite video game, Honkai: Star Rail, up and running.

The miHoYo server room is broken up into a single corridor of sections, some of which have servers installed. Some of the servers are already turned on.

Audrey urgently needs to turn on more servers. However, the server room has bad ventilation, so if two servers in adjacent sections are both on, then the room will overheat.

Audrey cannot turn off servers that are already on. Compute the maximum number of servers Audrey can turn on from the ones that are currently off without causing the room to overheat.

입력

The first line of input contains a single integer, $n$ ( $1 \le n \le 3 \cdot 10^5$ ).

The second line of input contains a ternary string $s$ of length $n$ , representing the room. A character of 0 represents a section with no server, a character of 1 represents a section with a server that is off, and a character of 2 represents a section with a server that is on.

It is guaranteed that the server room is not currently overheating.

출력

Output a single number, the number of additional servers Audrey can turn on from the ones that are currently off.

예제3

예제 1
입력
```
7
1112111
```
예상 출력
```
2
```
예제 2
입력
```
3
212
```
예상 출력
```
0
```
예제 3
입력
```
3
101
```
예상 출력
```
2
```