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

У фермера Джона N (1 ≤ N ≤ 10000) коров выстраиваются для вечернего доения. Каждая корова имеет свой уровень "раздражения" в диапазоне 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).