Нові втрати ворога

Обмеження: 1 сек., 256 МіБ

Щодня зранку кожен українець відкриває зведення Генштабу, щоб побачити яких втрат поніс ворог за минулий день. Марічка робить це і до того ж записує дані про втрати ворога на картках (одне число на одній картці). Проте на відміну від Зеника, кожного дня вона записує сумарні втрати ворога з моменту початку війни.

Марічка записувала втрати щодня впродовж \(n\) днів, але раптом помітила, що всі її картки змішались. От халепа! Тож тепер її ціль — відновити правильну послідовність втрат. Оскільки кількість втрат ворога зростає кожного дня, то це зробити дуже просто!

Зеник, друг Марічки, запропонував їй викласти всі картки в ряд зліва направо та робити такі дії: допоки послідовність не відновлена, Марічка повинна вибрати дві сусідні картки, такі що різниця чисел (число на лівій картці мінус число на правій) на них максимально можлива, та поміняти їх місцями. Якщо пар карток з максимальною різницею декілька, то вона повинна вибрати найлівішу таку пару.

Наприклад, якщо у Марічки є картки з числами \(7\), \(47\) та \(4\), то вона діятиме таким чином:

• поміняє місцями картки \(47\) та \(4\), адже різниця у цій парі \(47 - 4 = 43\) є більшою за різницю у іншій парі \(7 - 47 = -40\)

• поміняє місцями картки \(7\) та \(4\), адже різниця у цій парі \(7 - 4 = 3\) є більшою за різницю у іншій парі \(4 - 47 = -43\)

• Марічка побачить, що послідовність втрат ворога стала коректною (4 вороги у перший день, 3 у другий та 40 у третій), тому вона закінчить впрорядковувати її;

Марічка вже розклала картки, та проте їй цікаво скільки часу займе це все дійство. Знаючи свої здібності, вона впевнена, що на те, щоб поміняти дві сусідні картки, їй необхідно рівно одна секунда. Більше того, шукає потрібну пару вона миттєво!

Чи можете Ви допомогти Марічці порахувати скільки часу їй потрібно буде, аби відновити правильну послідовність?

Вхідні дані

У першому рядку задані одне ціле число \(n\) — кількість днів, у які Марічка записувала статистику.

У наступному рядку через пробіл задано \(n\) чисел \(a_i\) — дані про сумарні втрати ворога відповідно до карток Марічки.

Вихідні дані

Виведіть одне число — скільки секунд Марічці знадобиться аби відновити коректну послідовність сумарних втрат ворога.

Обмеження

\(1 \le n \le 5000\),

\(1 \le a_i \le 10^9\),

10 балів: \(n \le 100\),

15 балів: без додаткових обмежень.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
3 7 47 4	2

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
1 146092572	0

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
5 6 4 3 1 5	7

Примітки

У другому тесті послідовність складається з лише однієї картки — тому вона точно є коректною.

У третьому тесті Марічка діятиме таким чином:

• поміняє місцями картки з числами 6 та 4

• поміняє місцями картки з числами 6 та 3

• поміняє місцями картки з числами 6 та 1

• поміняє місцями картки з числами 3 та 1

• поміняє місцями картки з числами 4 та 1

• поміняє місцями картки з числами 4 та 3

• поміняє місцями картки з числами 6 та 5

Загалом вона витратить 7 секунд на ці дії.