Yet Another Contest 7 P1 - Page Turning

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

Josh is a pianist! He wants to learn N 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 1 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 i-th of the N pieces has a_i 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?


1 \le N \le 10^6

1 \le a_i \le 10^9

Subtask 1 [50%]

a_i is odd for all 1 \le i \le N.

Subtask 2 [50%]

No additional constraints.

Input Specification

The first line contains a single integer, N.

The second line contains N space-separated integers, a_1, a_2, \dots, a_N.

Output Specification

On the first line, output the smallest possible sum of the inconveniences of the pieces.

On the second line, output N space-separated integers, containing a permutation of the integers 1, 2, \dots, N. This should represent an optimal order in which the pieces should be concatenated, with pieces earlier in the manuscript outputted first.

Sample Input

3 5 4

Sample Output

1 3 2


Suppose Josh concatenates the 1-st piece, the 3rd piece, and then the 2-nd piece, in that order.

The first piece spans pages 1 to 3, and has an inconvenience of 1, since a page turn is required to move from page 1 to page 2.

The third piece spans pages 4 to 7, and has an inconvenience of 1, since a page turn is required to move from page 5 to page 6.

The second piece spans pages 8 to 12, and has an inconvenience of 2, since page turns are required to move from page 9 to page 10 and from page 11 to page 12.

The sum of the inconveniences of the pieces is 1 + 1 + 2 = 4, which can be proven to be optimal.


There are no comments at the moment.