Substring in h-Transformed Binary Strings

Let \(h\) be a function that acts on strings composed of the digits 0 and 1. The function \(h\) transforms a string \(w\) by replacing every occurrence of 0 with 1 and every occurrence of 1 with \(10\) simultaneously. In other words,

[ \begin{aligned} h(0) &= 1,\ h(1) &= 10. \end{aligned} ]

For any nonnegative integer \(k\), we denote by \(h^k\) the function \(h\) composed with itself \(k\) times. In particular, \(h^0\) is the identity function and \(h^0(w)=w\). Consider the sequence defined by \(h^k(\mathtt{0})\) for \(k=0,1,2,3,\ldots\). The first few terms are:

• \(h^0(\mathtt{0}) = \mathtt{0}\)
• \(h^1(\mathtt{0}) = \mathtt{1}\)
• \(h^2(\mathtt{0}) = \mathtt{10}\)
• \(h^3(\mathtt{0}) = \mathtt{101}\)
• \(h^4(\mathtt{0}) = \mathtt{10110}\)
• \(h^5(\mathtt{0}) = \mathtt{10110101}\)

Given a sequence of nonnegative integers \(k_1, k_2, \ldots, k_n\), consider the string

[ X = h^{k_1}(\mathtt{0}) \cdot h^{k_2}(\mathtt{0}) \cdots h^{k_n}(\mathtt{0}). ]

A string \(x\) is called a substring of a string \(y\) if it occurs in \(y\) as a contiguous block. The problem is to determine whether there exists an integer \(m\) such that \(X\) is a substring of \(h^m(\mathtt{0})\).

Observation: Notice that every string of the form \(h^k(\mathtt{0})\) (for any \(k\)) does not contain the block \(\mathtt{00}\). In fact, one can verify that for \(k \ge 1\), \(h^k(\mathtt{0})\) always starts with \(\mathtt{1}\) and has the following ending pattern:

• If \(k\) is even (or \(k=0\)), \(h^k(\mathtt{0})\) ends with \(\mathtt{0}\).
• If \(k\) is odd and \(k \ge 1\), it ends with \(\mathtt{1}\).

Thus, the only possibility for the concatenation X to introduce a \(\mathtt{00}\) block is at the junction between two consecutive segments: if the first segment ends with \(\mathtt{0}\) (which happens when its corresponding exponent is even) and the following segment starts with \(\mathtt{0}\) (this happens only when the exponent is 0). Therefore, \(X\) will be a substring of \(h^m(\mathtt{0})\) for some \(m\) if and only if the concatenated string does not contain \(\mathtt{00}\).

Task: Given \(n\) and \(k_1,k_2,\ldots,k_n\), output YES if there exists an \(m\) such that

[ X = h^{k_1}(\mathtt{0}) h^{k_2}(\mathtt{0}) \cdots h^{k_n}(\mathtt{0}) ]

is a substring of (h^m(\mathtt{0})), and output NO otherwise. In summary, the answer is YES if and only if no two consecutive segments in the sequence create a boundary with the digits "00". Given that for any (k \ge 1), (h^k(\mathtt{0})) starts with (\mathtt{1}) and only (h^0(\mathtt{0})) = "0", the condition is violated if for some index (i), (h^{k_i}(\mathtt{0})) (with even (k_i)) is immediately followed by (h^0(\mathtt{0})).

inputFormat

The input consists of two lines:

1. The first line contains a single integer \(n\) representing the number of integers in the sequence.
2. The second line contains \(n\) space-separated nonnegative integers \(k_1, k_2, \ldots, k_n\).

outputFormat

Output a single line containing either YES or NO (without quotes). Output YES if there exists an integer \(m\) such that the concatenated string X is a substring of \(h^m(\mathtt{0})\); otherwise, output NO.

Hint: Since every string \(h^k(\mathtt{0})\) with \(k\ge1\) always starts with \(\mathtt{1}\) and only \(h^0(\mathtt{0}) = \mathtt{0}\), the only check needed is to ensure that no instance of \(\mathtt{00}\) is formed at the junctions of the segments.

sample

2
1 0

YES