Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

L. Linesweeper
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice is an amateur Linesweeper player who is learning how to play the game!

In Linesweeper, mines are randomly placed on a board that consists of a single row with $$$N$$$ cells, numbered from $$$1$$$ to $$$N$$$ from left to right. Some cells contain mines while some cells do not contain mines.

Initially, all cells are unopened, and no information will be displayed. In each move, a player selects an unopened cell to open it. If the chosen cell contains a mine, the player loses immediately. Otherwise, a number is displayed in the opened cell, indicating how many adjacent cells contain mines. Two cells are considered adjacent if they share a side. As each cell has at most two adjacent cells, the number displayed in an opened cell will be 0, 1, or 2.

Alice has not lost yet. Thus, all opened cells do not contain mines. However, she is struggling to solve her Linesweeper; therefore, she shares the current board and seeks your help. Can you determine how many unopened cells she can open in her next move that are guaranteed not to contain mines?

Input

The first line consists of a single integer, $$$N$$$ ($$$1\leq N \leq10^5$$$), the number of cells.

The second line contains a string of length $$$N$$$, consisting only of the characters 0, 1, 2, and ?. If the $$$i$$$-th character is ?, the $$$i$$$-th cell is unopened. If the $$$i$$$-th character is 0, 1, or 2, it represents the number of mines adjacent to the $$$i$$$-th cell.

The information provided is guaranteed to be consistent and all opened cells do not contain mines.

Output

Output a single integer: the number of unopened cells that are guaranteed not to contain mines.

Examples
Input
3
?1?
Output
0
Input
7
0??2?1?
Output
2
Input
4
?11?
Output
0
Note

In Sample $$$1$$$, we can only determine that either the $$$1$$$-st or $$$3$$$-rd cell contains a mine. However, we cannot deduce exactly which one contains a mine. Therefore, there are no unopened cells that are guaranteed not to contain mines.

In Sample $$$2$$$, since there is no mine next to the $$$1$$$-st cell, we can deduce that the $$$2$$$-nd cell does not contain a mine. In the $$$4$$$-th cell, there should be $$$2$$$ mines adjacent to it; therefore, we can deduce that the $$$3$$$-rd and $$$5$$$-th cells contain mines. Since the $$$5$$$-th cell contains a mine and there is only $$$1$$$ mine next to the $$$6$$$-th cell, we can deduce that the $$$7$$$-th cell does not contain a mine. Therefore, the $$$2$$$-nd and $$$7$$$-th cells are guaranteed not to contain mines.

In Sample $$$3$$$, we can deduce that the $$$1$$$-st and $$$4$$$-th cells contain mines. Therefore, there are no unopened cells that are guaranteed not to contain mines.