Щоразу, коли Діма просить Оксану погуляти, вона зайнята виконанням домашнього завдання. Діма хоче допомогти їй закінчити це швидше, але нічого не виходить! Чи можете ви допомогти йому виконати домашнє завдання Оксани, щоб вона могла з ним погуляти?

Розглянемо масив ~A~, який містить ~N~ різних цілих чисел ~A_0 A_1 \cdots A_{n-1}~. Діма може міняти місцями будь-які два елементи масиву будь-яку кількість разів. Масив стане гарним, якщо сума ~|A_i - A_{i-1}|~ мінімальна для (~0 < i < n~).

Для даного масиву визначте та поверніть мінімальну кількість обмінів, які слід виконати, щоб зробити масив гарним.

Input

Перший рядок вхідного потоку містить ціле число ~N~.

Наступний рядок містить ~N~ цілих чисел ~A_i~.

Числа у рядку розділяються пропуском.

Output

У вихідний потік вивести відповідь.

Обмеження

~1 \le N \le 10^5~

~1 \le A_i \le 2 \times 10^9~

Пояснення

Обмінюємо місцями 3 і 7.

Далі обмінюємо 7 і 15.

Тепер масив гарний :)

Sample Input 1

4
7 15 12 3

Sample Output 1

2