Deck of Cards

Let:

• $a$ = number of 0 operations
• $b$ = number of 1 operations
• $c$ = number of 2 operations

A 0 always removes from the top. Since the deck starts as $1,2,\dots,n$, after all operations, at least the first $a$ cards must be removed.

A 1 always removes from the bottom, so at least the last $b$ cards must be removed.

The only annoying part is 2, but it is not actually that annoying. Each 2 can be treated as choosing either:

• one more top removal, or
• one more bottom removal.

So if $x$ of the 2 operations are used on the top, then:

$$\text{top removals} = a + x$$

and since the other $c-x$ go to the bottom:

$$\text{bottom removals} = b + (c-x)$$

where $0 \le x \le c$.

That means the number of cards removed from the top can be any value from $a$ to $a+c$. The exact order of operations does not change this. Removing from ends is boring in a useful way: only the final counts matter.

Guaranteed removed cards

Cards $1$ through $a$ are removed no matter what, because even with every 2 sent to the bottom, the $a$ forced top removals still happen.

Cards $n-b+1$ through $n$ are also removed no matter what, because of the $b$ forced bottom removals.

So these positions get -.

Guaranteed remaining cards

A card can only be removed from the top if it is among the first $a+c$ cards, because that is the maximum possible number of top removals.

A card can only be removed from the bottom if it is among the last $b+c$ cards.

So a card is definitely safe only if it is outside both danger zones:

$$a+c < i \le n-b-c$$

Those positions get +.

If this interval is empty, then no card is guaranteed to remain. That is fine. Sometimes the deck is basically Schroedinger's cardboard.

Uncertain cards

Every remaining card is ?.

Why? Because it is not forced to be removed, but it is also within reach of some assignment of the 2 operations. For example, a card near the top can be removed if enough 2s are spent on top, but it can survive if those 2s are spent on bottom instead. Same idea near the bottom.

So the construction is simple:

1. Start the answer as all ?.
2. Mark the forced top segment $[1,a]$ as -.
3. Mark the forced bottom segment $[n-b+1,n]$ as -.
4. Mark the definitely-safe middle segment $(a+c,\ n-b-c]$ as +.

This is $O(n)$ per test case, which is comfortably fine because the total $n$ is at most $2\cdot 10^5$.