Задача №111911. Джекпот
Вася решил испытать удачу и свои математические способности в зале игровых автоматов. Там он нашел интересный автомат, процесс игры в котором устроен следующим образом.
Игроку дается n шаров, на каждом из шаров написано натуральное число. После этого игрок должен разместить шары по n лункам так, чтобы штраф был минимален. Лунки расположены на одной прямой и пронумерованы от 1 до n слева направо.
Штраф вычисляется следующим образом: берется сумма штрафа по всем лункам, штраф за i -ую лунку равен i · a i , где a i — число, написанное на шаре, лежащем в i -ой лунке.
Помогите Васе расположить шары так, чтобы минимизировать штраф и получить максимальную прибыль.
В первой строке дано число n — количество шаров ( 1 ≤ n ≤ 10 5 ). Во второй строке даны n натуральных чисел, которые написаны на шарах. Числа не превышают 10 9 .
Выведите n чисел — числа, написанные на шарах в порядке их распределения по лункам. То есть первое число, это число, написанное на шаре в первой лунке, далее для второй лунки и так далее до n -ой.
В исходном примере штраф будет равен 1·2 + 2·1 + 3·1 = 7 . Это наименьший возможный штраф.
3 1 2 1
2 1 1