Minesweeper Arrangements

This problem is a simplified version of Minesweeper set on an n × 2 board. In this board, only the cells in the first column may contain mines, while the second column is guaranteed to be mine-free. For every cell in the second column, a number is given which represents the total number of mines in its adjacent (8-connected) cells. Since the second column is safe, its number is determined solely by the mines in the first column which can be adjacent either directly or diagonally.

More precisely, consider a board with n rows (indexed from 1 to n) and exactly 2 columns. Let a[i] be a binary variable indicating whether the cell in row i of the first column contains a mine (1 for a mine, 0 for safe). Then the cell in the second column of row i shows a number d[i] defined as follows:

• If i = 1: d[1] = a[1] + a[2] (if n > 1)
• If i = n (and n > 1): d[n] = a[n-1] + a[n]
• Otherwise (1 < i < n): d[i] = a[i-1] + a[i] + a[i+1]

Your task is to count how many valid arrangements of mines in the first column can satisfy these constraints given the numbers d[1]...d[n] for the second column.

Note: If n = 1, the only neighbor of the second column cell is the cell (1,1), so d[1] must equal a[1].

All formulas are provided in LaTeX format. For example, the rule for interior cells is given as: $$d_i = a_{i-1}+a_i+a_{i+1}$$ for \(2 \le i \le n-1\).

inputFormat

The first line contains a single integer \(n\) (\(1 \le n \le 10^5\)), the number of rows. The second line contains \(n\) integers \(d_1, d_2, \dots, d_n\), where each \(d_i\) represents the number in the second column of row \(i\), as described above.

outputFormat

Output a single integer: the number of valid mine arrangements in the first column that satisfy the constraints given by \(d_i\) for each row.

sample

1
1

1