ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

1663. The Hobbit or There and Back Again 2

Time limit: 0.5 second
Memory limit: 64 MB
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