### 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
*C*_{1}, C_{2} and *C*_{3},
of heights 4, 2 and 4 metres, respectively. If he chose to
arrange them in the order *C*_{1} C_{2}
C_{3} then he would have to climb 12 metres (4
metres to reach the top of *C*_{1}, descend 2
metres, jump to the top of *C*_{2}, jump across to
*C*_{3}, climb 2 metres to reach the top of
*C*_{3} and finally climb down 4 metres from the
top of *C*_{3}, adding up to 12 metres). Instead,
if he were arrange these cylinders in the sequence
*C*_{3} C_{1} C_{2} 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 *h*_{i},
indicating the height of cylinder *i*.

Output format

The output must consist of *N* lines, each containing
one integer *a*_{i} (1 ≤ *a*_{i}
≤ *N*), so that the sequence *a*_{1}
a_{2} ... a_{N} 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.

Example

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

Sample input:

3
4
2
4

Sample output:

3
1
2

Test data: