GamingForces
Contest: Educational Codeforces Round 142 (Rated for Div. 2)
Difficulty rating: 800
Tags: greedy, sortings

Monocarp is playing a computer game. He's going to kill $$$n$$$ monsters, the $$$i$$$-th of them has $$$h_i$$$ health.

Monocarp's character has two spells, either of which he can cast an arbitrary number of times (possibly, zero) and in an arbitrary order:

- choose exactly two alive monsters and decrease their health by $$$1$$$;
- choose a single monster and kill it.

When a monster's health becomes $$$0$$$, it dies.

What's the minimum number of spell casts Monocarp should perform in order to kill all monsters?

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.

The first line of each testcase contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$) — the number of monsters.

The second line contains $$$n$$$ integers $$$h_1, h_2, \dots, h_n$$$ ($$$1 \le h_i \le 100$$$) — the health of each monster.

The sum of $$$n$$$ over all testcases doesn't exceed $$$2 \cdot 10^4$$$.

Output format:
For each testcase, print a single integer — the minimum number of spell casts Monocarp should perform in order to kill all monsters.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first testcase, the initial health list is $$$[1, 2, 1, 2]$$$. Three spells are casted:

- the first spell on monsters $$$1$$$ and $$$2$$$ — monster $$$1$$$ dies, monster $$$2$$$ has now health $$$1$$$, new health list is $$$[0, 1, 1, 2]$$$;
- the first spell on monsters $$$3$$$ and $$$4$$$ — monster $$$3$$$ dies, monster $$$4$$$ has now health $$$1$$$, new health list is $$$[0, 1, 0, 1]$$$;
- the first spell on monsters $$$2$$$ and $$$4$$$ — both monsters $$$2$$$ and $$$4$$$ die.

In the second testcase, the initial health list is $$$[2, 4, 2]$$$. Three spells are casted:

- the first spell on monsters $$$1$$$ and $$$3$$$ — both monsters have health $$$1$$$ now, new health list is $$$[1, 4, 1]$$$;
- the second spell on monster $$$2$$$ — monster $$$2$$$ dies, new health list is $$$[1, 0, 1]$$$;
- the first spell on monsters $$$1$$$ and $$$3$$$ — both monsters $$$1$$$ and $$$3$$$ die.

In the third testcase, the initial health list is $$$[1, 2, 3, 4, 5]$$$. Five spells are casted. The $$$i$$$-th of them kills the $$$i$$$-th monster with the second spell. Health list sequence: $$$[1, 2, 3, 4, 5]$$$ $$$\rightarrow$$$ $$$[0, 2, 3, 4, 5]$$$ $$$\rightarrow$$$ $$$[0, 0, 3, 4, 5]$$$ $$$\rightarrow$$$ $$$[0, 0, 0, 4, 5]$$$ $$$\rightarrow$$$ $$$[0, 0, 0, 0, 5]$$$ $$$\rightarrow$$$ $$$[0, 0, 0, 0, 0]$$$.

Example input:
3
4
1 2 1 2
3
2 4 2
5
1 2 3 4 5

Example output:
3
3
5

Editorial:
The first spell looks pretty weak compared to the second spell. Feels like you almost always replace one with another. Let's show that you can totally avoid casting the spell of the first type twice or more on one monster.
Let the two first spell casts be $$$(i, j)$$$ and $$$(i, k)$$$ for some monsters $$$i, j$$$ and $$$k$$$. You can replace them by a cast of the second spell on $$$i$$$ and a cast of the first spell on $$$(j, k)$$$. That would deal even more damage to $$$i$$$ and the same amount to $$$j$$$ and $$$k$$$. The number of casts doesn't change.
Thus, it only makes sense to use the first spell on monsters with $$$1$$$ health. Calculate the number of them, kill the full pairs of them with the first spell, and use the second spell on the remaining monsters.
Overall complexity: $$$O(n)$$$ per testcase.