e-olymp
favorite Нам необходимо немного Вашей помощи чтобы сайт продолжал работать, нажмите на банер чтобы узнать больше.
Задачи

Коровья сортировка

Коровья сортировка

У фермера Джона N (1N10000) коров выстраиваются для вечернего доения. Каждая корова имеет свой уровень "раздражения" в диапазоне 1...100000. Естественно, что более раздраженные коровы приносят больший ущерб доильному оборудования, но так как с течением времени раздражение коров постепенно угасает, фермер Джон хочет их изначально расположить так, чтобы более раздраженные коровы попадали на доение позже. Перемещение в очереди двух коров занимает определенное время, которое зависит от их раздраженности. Известно, что нужно затратить время X+Y для изменения порядка двух коров, имеющих степени раздраженности X и Y соответственно.

Помогите фермеру Джону определить минимальное время для изменения порядка построения коров.

Входные данные

Строка 1: Одно целое число: N.
Строки 2..N+1: Каждая строка содержит одно целое число: строка i+1 описывает раздраженность коровы i.

Выходные данные

Строка 1: Минимальные затраты времени для упорядочения коров в порядке возрастания из раздражения.

Примечание

2 3 1 : Начальное расположение.
2 1 3 : После перестановки коров с раздражительностью 3 и 1 (время = 1+3 = 4).
1 2 3 : После перестановки коров с раздражительностью 1 и 2 (время = 2+1 = 3).
Лимит времени 2 секунды
Лимит использования памяти 64 MiB
Входные данные #1
3
2
3
1
Выходные данные #1
7