Josh is a pianist! He wants to learn different pieces, but first, he wants to combine them into a single manuscript.
The manuscript will be laid out in the same format as a normal book; pages are numbered sequentially from onwards, with odd pages on the right and even pages on the left. When moving from an odd page to the following even page, a page turn is required.
When Josh plays a piece, he opens the manuscript such that it displays the first page of that piece. He then plays the piece, turning pages so that each page in the piece is displayed sequentially. The inconvenience of that piece is defined as the number of page turns required when playing that piece.
The -th of the pieces has pages. He wants to reorder the pieces so that when the manuscript is constructed by concatenating the pieces in that order, the sum of the inconveniences of all pieces is minimised.
Can you help Josh find the smallest possible sum of inconveniences of the pieces, and any ordering which achieves this value?
Subtask 1 [50%]
is odd for all .
Subtask 2 [50%]
No additional constraints.
The first line contains a single integer, .
The second line contains space-separated integers, .
On the first line, output the smallest possible sum of the inconveniences of the pieces.
On the second line, output space-separated integers, containing a permutation of the integers . This should represent an optimal order in which the pieces should be concatenated, with pieces earlier in the manuscript outputted first.
3 3 5 4
4 1 3 2
Suppose Josh concatenates the -st piece, the rd piece, and then the -nd piece, in that order.
The first piece spans pages to , and has an inconvenience of , since a page turn is required to move from page to page .
The third piece spans pages to , and has an inconvenience of , since a page turn is required to move from page to page .
The second piece spans pages to , and has an inconvenience of , since page turns are required to move from page to page and from page to page .
The sum of the inconveniences of the pieces is , which can be proven to be optimal.