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

Limits: 1 sec., 256 MiB

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

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

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

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

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

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

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

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

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

Input

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

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

Output

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

Constraints

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

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

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

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

Samples

Input (stdin) сopy	Output (stdout) сopy
3 7 47 4	2

Input (stdin) сopy	Output (stdout) сopy
1 146092572	0

Input (stdin) сopy	Output (stdout) сopy
5 6 4 3 1 5	7

Notes

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

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

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

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

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

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

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

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

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

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