Consider the sequence \(y\) obtained by flipping the \(2\)-nd, \(4\)-th, \(6\)-th, \(\cdots\) terms from the beginning of \(x\). Let us also flip the \(2\)-nd, \(4\)-th, \(6\)-th, \(\cdots\) terms of \(A\) and aim to make \(y\) equal to this \(A\).

By rephrasing the operations on \(x\) to those on \(y\), we get the following:

• Operation A: Add \(0\) to the beginning of \(y\).
• Operation B: Add a value to the end of \(y\). The value to add depends on the parity of the length of \(y\) before the addition: we add \(0\) if the length is even and \(1\) if it is odd.

First of all, we need \(A_1=0\) to hold. If all elements of \(A\) are \(0\), the answer is yes.

Otherwise, let \(A_z\) be the position of the \(1\) nearest to the beginning of \(A\). Let us take out \(A_z\) and the following elements from \(A\) and call this part of the sequence \(S\). Consider making \(S\) by doing only Operation B. Then, we need \(S\) to be a subsequence of \((0,1,0,1,...)\) (length \(N\)). On the other hand, if this holds, we can make \(y\) equal to \(A\) by doing Operation B for a position in \((0,1,0,1,...)\) corresponding to \(S\) and Operation A for the other positions.

These procedures can be implemented in \(O(N)\).

Sample submission (c++)