Consider an array of n distinct integers, A = [a₀, a₁,, a_n-1] . You can swap any two elements of the array any number of times. An array is beautiful if the sum of |a_i a_i-1| among 0 < i < n is minimal possible (after, possibly, performing some swaps).

Given the array A, find and print the minimum number of swaps that should be performed to make the array beautiful.

Input Format

The first line contains a single integer, n, denoting the number of elements in the array A. The second line contains n space-separated integers describing the respective distinct values of a₀, a₁,,a_n-1.

Constraints

1 ? n ? 10⁵

¹ ? a_i ? 2 * 10⁹

Output Format

Print the minimum number of swaps that should be performed in order to make the array beautiful.

Sample Input

4

2 5 3 1

Sample Output

2

Explanation

Let's define array B = [1,2,3,5] to be the beautiful reordering of array A, as the sum of the absolute values of differences between its adjacent elements is minimal among all permutations and only two swaps (1 with 2 and then 2 with 5) was performed.

(write on eclipse)