The strategy for this game is to arrange the largest ~\lfloor \frac{N}{2} \rfloor~ integers into the odd indices. When the demon king takes a number from an even index, it gets one of the smallest ~\lfloor \frac{N}{2} \rfloor~ integers, and all the integers above automatically switch parities. To reverse this parity switch, we take the index under the one that the demon king takes, getting one of the largest ~\lfloor \frac{N}{2} \rfloor~ integers and switching all the integers above back into the parities they started with. We simply repeat this until all the integers are gone. In the end, we can always end up with the largest ~\lfloor \frac{N}{2} \rfloor~ integers in our collection, leaving the smallest ~\lfloor \frac{N}{2} \rfloor~ integers for the demon king.

Time Complexity: ~\mathcal{O}(N \log N)~