Indian National Olympiad in Informatics

Online Programming Contest, 6-7 November 2004


Basic Division

Problem 1: The Lazy Circus Gymnast, (K Narayan Kumar, CMI)

One of the highlights of the shows of the Ennui Circus Company is the performance by Palli, "The Incredible Lizard Man". As his stage name suggests, Palli can climb up and down any vertical surface - trees, walls, ropes, ...

For his performance, a set of smooth steel cylinders of varying heights are arranged in a line. Palli then climbs up to the top of each of these cylinders. To save himself some work (and to make the show interesting) he does not climb all the way down from a cylinder to move to the next. If the next cylinder is taller than the present one, he simply jumps across horizontally from the top of the current cylinder, latches onto the side of the next one and climbs up from there. If the next cylinder is shorter than the present one, he comes down from the top of the current cylinder till he is at the same level as the top of the next one and then jumps across horizontally.

Palli is very lazy and he would like to minimize the amount of climbing up and down that he has to do during his show. He has a limited choice in this matter because the circus owner has already purchased the set of cylinders to be used. All that Palli can do is to rearrange these cylinders in any sequence he wants. He would like to choose an arrangement that minimizes his work.

For example, suppose there are three cylinders C1, C2 and C3, of heights 4, 2 and 4 metres, respectively. If he chose to arrange them in the order C1 C2 C3 then he would have to climb 12 metres (4 metres to reach the top of C1, descend 2 metres, jump to the top of C2, jump across to C3, climb 2 metres to reach the top of C3 and finally climb down 4 metres from the top of C3, adding up to 12 metres). Instead, if he were arrange these cylinders in the sequence C3 C1 C2 then he only needs to climb 8 metres.

Your task is to help him find an arrangment of the cylinders that minimizes the amount he has to climb up and down.

Input format

The first line of the input consists of an integer N indicating number of cylinders. The next N lines (i.e. lines 2,..., N+1) provide information on the heights of the cylinders. Line i+1, (1 ≤ i ≤ N) contains a single integer hi, indicating the height of cylinder i.

Output format

The output must consist of N lines, each containing one integer ai (1 ≤ aiN), so that the sequence a1 a2 ... aN describes a optimal way of arranging the cylinders 1,...,N. If there is more than one optimal arrangement, it suffices to print any one.

Test data

You may assume that 3 ≤ N ≤ 5000.


We now illustrate the input and output formats using the example described above.

Sample input:


Sample output:


Test data:

Copyright (c) IARCS 2003-2018;   Last Updated: 25 Nov 2004