Old Bilbo collects songs and sagas of all races of Middle-earth. Every twenty
years he leaves Rivendell for a year to travel through N cities of the
Middle-earth, numbered from 1 to N (Rivendell has number 1), and comes back
at the end of the journey. Nineteen years have passed since Bilbo's last
journey, so he started to prepare for travelling. From his last journey Bilbo
remembers that there is a warder at the entrance to each city. He asks the
travelers what city they came from and requires an entrance fare depending
on that. Time passed, and the entrance fee has changed since the last journey.
From the King of Elves Elrond Bilbo has learnt that, if a traveler
arrives to a city with number A from a city with number B, the warder will
require exactly PA·[1000/PB] gold coins, where
Pi is the population of city with number i and [X] denotes
the floor of X. Officials think that it will stimulate the population outflow from
the bigger cities to the smaller ones. Bilbo knows a population of all cities of
Middle-earth and supposes that it will not change during the year of his journey.
As usual, before the journey he would like to know the order of visiting the cities
which will minimize the total amount of money paid.
The first line contains an integer N. 2 ≤ N ≤ 1000. The second line contains
N integers P1, …, PN, delimited with spaces — the
populations of the cities of Middle-earth. All Pi lie in range from 1 to 1000.
Output N integers — order of visiting N cities
which minimizes the total entrance fee. Remember that Bilbo starts his travel
from the city with number 1, visits each city exactly once and returns to the
city with number 1 only in the end. If there are several solutions, you may
output any one of them.
10 3 5 4
1 4 2 3
Problem Author: Alexander Ipatov
Problem Source: Ural SU Contest. Petrozavodsk Winter Session, January 2008