Triple Removal

Let the queried subarray have length $m$.

First: When Is It Possible?

Every operation removes exactly three equal values. So the number of $0$s and the number of $1$s are independent constraints:

$$cnt_0 \equiv 0 \pmod 3, \qquad cnt_1 \equiv 0 \pmod 3.$$

If either one fails, the answer is $-1$. No operation order can fix bad divisibility. Arithmetic is annoyingly undefeated.

Assume from now on that both counts are divisible by $3$.

Lower Bound

Each operation removes $3$ elements, so we need exactly

$$\frac{m}{3}$$

operations.

For any chosen triple $i<j<k$, the cost is

$$\min(k-j, j-i).$$

Both gaps are positive, so every operation costs at least $1$. Therefore:

$$\text{answer} \ge \frac{m}{3}.$$

The whole problem is now: when can we make every operation cost exactly $1$?

Cost 1 Means Adjacent Equal Elements

A triple removal costs $1$ exactly when two of the three chosen equal elements are adjacent in the current array.

So if the array has an adjacent equal pair, say 00 or 11, we can use that pair plus one more equal value to perform a cost-$1$ removal.

Because that value's count is divisible by $3$, having two copies means there is a third copy unless the range was impossible, which we already filtered out.

The Only Bad Shape Is Alternating

If a binary array has no adjacent equal pair, then it must be perfectly alternating:

$$010101\ldots$$

or

$$101010\ldots$$

In that shape, equal values are separated by at least one opposite value. The closest three equal elements have gaps $2$ and $2$, so the first move costs at least $2$. It can also cost exactly $2$, by taking three consecutive occurrences of one value.

After removing those three equal elements, the other value gets glued together somewhere, so the remaining array now has adjacent equal elements. From then on, the lower bound is reachable.

So for a valid alternating range:

$$\text{answer}=\frac{m}{3}+1.$$

Why Non-Alternating Ranges Reach the Lower Bound

If the range is not alternating, it has at least one adjacent equal pair.

There is a useful run-based fact:

In any valid non-alternating binary array, we can remove some cost-$1$ triple so that the remaining array is either empty or still non-alternating.

Why? Look at runs of equal values. Since the array is non-alternating, some run has length at least $2$. We remove two adjacent elements from such a run and choose the third equal element so that either:

• a same-valued run still has length at least $2$, or
• deleting a whole internal run glues two opposite-valued neighboring runs together.

If neither can be done, then every run must have length $1$, which means the array was alternating in the first place. Contradiction.

So by induction, a valid non-alternating range can be fully deleted with cost $1$ per operation. Therefore:

$$\text{answer}=\frac{m}{3}.$$

Answering Queries

For each query $[l,r]$:

1. Compute the number of ones with a prefix sum.
2. Compute zeros from length minus ones.
3. Check whether there is any equal adjacent pair inside the range.

Precompute:

$$same[i] = [a_i = a_{i+1}]$$

and prefix sums of same. Then $[l,r]$ is alternating iff

$$\sum_{i=l}^{r-1} same[i] = 0.$$

So the logic is:

• if $cnt_0 \bmod 3 \ne 0$ or $cnt_1 \bmod 3 \ne 0$, print $-1$;
• else if the range is alternating, print $m/3+1$;
• otherwise print $m/3$.

The preprocessing is $O(n)$ and each query is $O(1)$, so each test case is $O(n+q)$.