e-olymp
Задачі

Коровяче сортування

Коровяче сортування

У фермера Джона 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
Вхідні дані
3
2
3
1
Вихідні дані
7