Xmas or Hysteria

Two things matter here: who dies, and who has already attacked. The health values look scary, but the core is pretty clean.

The basic fight fact

Sort the elves by attack:

$a_{p_1}<a_{p_2}<\cdots<a_{p_n}.$

In any fight between two living elves, the weaker elf always dies. Why? Its current health is never more than its original value, and it loses the stronger elf's attack value, which is larger.

The stronger elf may survive or may also die if it was already damaged. But if it is fresh enough and only loses a weaker attack value, it survives.

So an attack

$p_i\to p_{i+1}$

kills $p_i$ and leaves $p_{i+1}$ alive. Therefore an increasing chain

$p_l\to p_{l+1},\ p_{l+1}\to p_{l+2},\ \ldots,\ p_{r-1}\to p_r$

kills the whole chain except $p_r$. This is the main hammer.

The stopping rule

The process stops only when there is no living elf that has not attacked and has another living elf to target.

So:

• with $0$ alive, it stops;
• with $1$ alive, it stops;
• with $m\ge2$ alive, every survivor must have attacked.

That last bullet is the classic trap. Leaving two untouched survivors is not a solution. The spell keeps going. Brutal, but fair.

Impossible: $m=n$

Initially $n\ge2$, all elves are alive, and nobody has attacked, so the process cannot stop immediately.

At least one attack must happen. The first attack kills the weaker of the two elves, so ending with all $n$ elves alive is impossible.

Case $m=1$

Always possible.

Just chain through all elves in increasing attack order:

$p_1\to p_2,\ p_2\to p_3,\ \ldots,\ p_{n-1}\to p_n.$

Every attacker dies, and the next elf survives. In the end only $p_n$ is alive. A single survivor does not need to have attacked, because there is nobody else to attack.

Case $m\ge2$

Every final survivor must have attacked.

A survivor cannot attack a stronger survivor, because then it would die. It also cannot attack a weaker survivor, because then the weaker survivor would die. So each survivor must spend its attack on some weaker elf that is supposed to die.

Those targets must be distinct, because a target dies immediately after being hit by a stronger survivor. Therefore we need at least $m$ dead elves:

$n-m\ge m.$

Equivalently:

$2m\le n.$

This condition is also enough.

Take the $m$ largest elves as survivors. The other $n-m$ elves are doomed. Since $n-m\ge m$, split the doomed elves into $m$ nonempty consecutive groups in sorted order.

For one group

$p_l,p_{l+1},\ldots,p_r$

assigned to survivor $s$, do the chain inside the group:

$p_l\to p_{l+1},\ p_{l+1}\to p_{l+2},\ \ldots,\ p_{r-1}\to p_r.$

Now only $p_r$ remains alive from that group. Then do

$s\to p_r.$

Since $s$ is one of the $m$ largest elves, it is stronger than every doomed elf. So $p_r$ dies, $s$ survives, and $s$ has attacked.

Do this for every group. Exactly the chosen $m$ survivors remain, and all of them have attacked, so the process is forced to stop.

Case $m=0$

Now everyone must die. Let $p_n$ be the maximum elf, with attack $M$.

The maximum elf can only lose health by interacting with weaker elves. Each weaker elf can damage it at most once, because that weaker elf dies immediately in such an interaction. So if

$\sum_{i=1}^{n-1} a_{p_i}<M,$

then the maximum elf can never die. Impossible.

Now suppose

$\sum_{i=1}^{n-1} a_{p_i}\ge M.$

We construct a full wipe.

First make the maximum attack the second maximum:

$p_n\to p_{n-1}.$

The second maximum dies, and $p_n$ remains alive with health

$M-a_{p_{n-1}}.$

Call this remaining health need.

Now look at the remaining elves $p_1,\ldots,p_{n-2}$. While the largest remaining elf has attack less than need, make that elf attack $p_n$. It dies, and need decreases by its attack. We only do this while its attack is strictly smaller than need, so $p_n$ stays alive.

Why can this loop not run out of elves? Initially the total attack of these remaining elves is at least need, because the total attack of all non-maximum elves is at least $M$. Every time we use an elf against $p_n$, both the remaining total and need decrease by the same amount. So eventually some remaining elf has attack at least need.

Once that happens, chain all still-unused remaining elves in increasing order, leaving the largest of them alive and not having attacked. Then this last elf attacks $p_n$.

Its attack is at least need, so $p_n$ dies. It also dies from recoil because $p_n$ is stronger. Now nobody is alive. Merry chaos.

Complexity

Sorting costs $O(n\log n)$ per test case. The construction prints at most $n$ attacks, and the total $n$ over all tests is bounded by $2\cdot10^5$.