Assignment # 4 Due Tuesday, October 31st 2017, 11.59 pm Consider an array of n distinct integers, A = [a0, a1,,an-1] . You can swap any two elements of the array any number of times. An array is beautiful if the sum of |ai ai-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 in order 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 a0, a1,,an-1. Constraints 1 n 105 1 ai 2 * 109 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.