Subtask 1

Every piece where ~a_i~ is odd will always have an inconvenience of ~\frac{a_i-1}{2}~, no matter where it is placed, so any ordering of the pieces is optimal. Therefore, we simply need to output the sum of all ~\frac{a_i-1}{2}~ along with any ordering.

Time complexity: ~\mathcal{O}(N)~

Subtask 2

Since pieces with odd lengths always have the same inconveniences, we should focus on the pieces where ~a_i~ is even. If the piece starts on an odd page, the inconvenience is ~\frac{a_i}{2}~, but if the piece starts on an even page, the inconvenience is only ~\frac{a_i}{2} - 1~.

It follows that we should maximise the number of pieces with even length that start on an even page. There are two possible cases:

• If there is at least one piece with an odd length, we should output one piece with a odd length, then all of the pieces with even lengths, then all the remaining pieces with odd lengths. This allows every piece with an even length to start on an even page.
• If every piece has an even length, then every piece will start on an odd page. Thus, the ordering of the pieces doesn't matter.

Time complexity: ~\mathcal{O}(N)~