Odd Process

Key observation

After each action, the bag sum is either $0$ or odd. If it becomes even, the cat clears it immediately.

Now suppose the final score is positive. Consider only the coins still in the bag after the last reset.

This final surviving segment starts from an empty bag. The first surviving coin cannot be even, because an even coin alone makes the sum even and gets deleted instantly. So it must be odd.

After that, the bag sum is odd:

• adding an even coin keeps it odd,
• adding an odd coin makes it even, so the bag gets cleared.

Therefore, the final bag must contain:

$$\text{exactly one odd coin and some number of even coins.}$$

That is the whole trick. Very small, very annoying, very Codeforces.

What can be discarded before the final bag?

Before the final surviving segment, the bag must end empty. Which coins can be thrown away like that?

Even coins are easy: from an empty bag, choosing one even coin immediately makes an even sum, so it gets cleared.

Odd coins must be discarded in pairs: odd plus odd gives an even sum, then the bag gets cleared.

So the discarded part is possible exactly when it contains an even number of odd coins.

The final bag itself contains one odd coin. Therefore, among the total $k$ selected coins, the number of selected odd coins must be odd.

Choosing coins

Let:

• $o$ be the number of odd coins,
• $m$ be the number of even coins.

For a fixed $k$, suppose we select $x$ odd coins. Then:

• $x$ must be odd,
• $1 \le x \le o$,
• $k-x \le m$.

Only one odd coin survives, so we always make the largest odd coin survive. The other selected odd coins are sacrificed before the final reset, so their values do not matter.

The $k-x$ selected even coins can all survive in the final bag, so we take the largest $k-x$ even coins.

Since all values are positive, we want to maximize $k-x$, which means minimizing feasible odd $x$.

So for each $k$:

$$x = \max(1, k-m)$$

because we need at least one odd, and we cannot select more than $m$ evens.

If $x$ is even, increase it by $1$ to make it odd.

If this final $x$ is greater than $o$ or greater than $k$, there is no way to end with a positive score, so the answer is $0$.

Otherwise:

$$\text{answer} = \max(\text{odd}) + \sum \text{largest } (k-x) \text{ even coins}.$$

Algorithm

1. Split the coins into odd and even arrays.
2. Sort both arrays descending.
3. Build prefix sums over the sorted even array.
4. For each $k$ from $1$ to $n$:
   • compute the smallest feasible odd count $x$,
   • force $x$ to be odd,
   • if valid, print largest odd plus the prefix sum of the largest $k-x$ evens,
   • otherwise print $0$.

Sorting dominates, so the complexity is $O(n \log n)$ per test case. Across all tests, this is easily within limits.