The Ancient Wizards' Capes

Let $b_i$ describe wizard $i$'s cape:

• $b_i=1$: cape on the left.
• $b_i=0$: cape on the right.

From position $i$, Harry sees:

• every left-cape wizard $j$ with $j\le i$,
• every right-cape wizard $j$ with $j\ge i$.

So

$$a_i = \#\{j\le i: b_j=1\}+\#\{j\ge i: b_j=0\}.$$

The important move: compare neighbors

Instead of trying to count $a_i$ from scratch, compare $a_i$ and $a_{i+1}$.

When Harry moves from position $i$ to $i+1$:

• Wizard $i$ stops being visible if wizard $i$ has a right cape.
• Wizard $i+1$ becomes visible if wizard $i+1$ has a left cape.

Everything else stays exactly the same. No hidden drama.

So:

$$a_{i+1}-a_i = b_{i+1} - (1-b_i).$$

Rearrange:

$$a_{i+1}-a_i = b_i+b_{i+1}-1.$$

Therefore every adjacent pair must satisfy:

$$b_i+b_{i+1}=a_{i+1}-a_i+1.$$

Since $b_i,b_{i+1}\in\{0,1\}$, the right side must be $0$, $1$, or $2$. That means every difference $a_{i+1}-a_i$ must be $-1$, $0$, or $1$, otherwise the answer is instantly $0$.

But we do not even need a separate check. The construction below naturally rejects bad values.

Why there are at most two answers

Once $b_1$ is chosen, the equation

$$b_i+b_{i+1}=a_{i+1}-a_i+1$$

forces

$$b_{i+1}=a_{i+1}-a_i+1-b_i.$$

So there are only two possible starting choices:

• $b_1=0$,
• $b_1=1$.

Each one either generates a valid binary sequence or crashes into something outside $\{0,1\}$.

That is the whole reason the count is tiny. The modulus looks scary, but the answer is never more than $2$. Classic Codeforces smoke machine.

The final absolute check

The adjacent equations only guarantee the differences between consecutive $a_i$ values. They do not guarantee the actual starting value $a_1$.

For a generated cape arrangement, let

$$L=\sum_{i=1}^n b_i$$

be the number of left-cape wizards.

At position $1$, Harry sees:

• wizard $1$ if $b_1=1$,
• every right-cape wizard, because all positions $j\ge 1$.

There are $n-L$ right-cape wizards, so the generated value is

$$a_1' = b_1 + (n-L).$$

The candidate arrangement is valid iff

$$a_1'=a_1.$$

If this holds, then all later values match too, because the adjacent differences were built to match.

Algorithm

For each test case:

1. Initialize answer $ans=0$.
2. Try $start=0$ and $start=1$ as $b_1$.
3. Generate the whole binary sequence using $$b_{i+1}=a_{i+1}-a_i+1-b_i.$$
4. If any generated value is not $0$ or $1$, reject this start.
5. Otherwise compute $L$, then check whether $$start+n-L=a_1.$$
6. If yes, increment $ans$.

Complexity is $O(n)$ per test case and $O(1)$ extra memory besides the input array.