class Result {

    /*
     * Complete the 'lilysHomework' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts INTEGER_ARRAY arr as parameter.
     */

    public static int lilysHomework(List<Integer> arr) {
    // Write your code here
        /*
        * Idea:
        - First, it can be proven that an arr with minimal difference between every two elements is a sorted array.
        - So the sorted array is the destination.
        - However, there are two results after sorting, increment and decrement array.
        - The final result is a solution with minimum swap.
        - A swap is called when an element is not in its final position, or at least, the values are distinct.
        - If an element is in its final value, it must not need to move.
        - Using minimum number of swaps theory to calculate the number of swaps
        - Numbers that need to be swapped form circles in which the length of the circle minus 1 is the number of swaps. 

        * Steps:
        - Calculate the minimum number of swaps in case increment list and decrement list.
         1. Create an object named "pair" that contains the value of the element and its primary index position.
         2. Get all the pair in a list, sort that list with customized comparator.
         3. Traverse through the pair list, using the graph theory to identify circles consisting the group of element need to be swapped.
         4. Specify the number of swaps.
         5. Get the total number in each order of the list. 
        - Find the minimum number of swaps between two ways.
        */
        
        List<Pair> arrPos = new ArrayList<>();
        for(int i = 0; i < arr.size(); i++){
            arrPos.add(new Pair(arr.get(i), i));
        }
        arrPos.sort(new Comparator<Pair>(){
            public int compare(
                Pair p1,
                Pair p2
            ){
                if(p1.value < p2.value){
                    return -1;
                } else if(p1.value == p2.value) return 0;
                else return 1;
            }
        });
        
        int res = 0, revRes = 0;
        boolean[] vis = new boolean[arrPos.size()];
        boolean[] revVis = new boolean[arrPos.size()];
        
        //Compare origin list with increment sorted list
        for(int i = 0; i < arrPos.size(); i++){
            
            if(vis[i] || arrPos.get(i).index == i) 
                continue;
            
            int circleLength = 0;
            int j = i;
            while(!vis[j]){
                vis[j] = true;
                circleLength ++;
                
                j = arrPos.get(j).index;
            }
            
            if(circleLength > 0) res += circleLength - 1;
        }
        
        //Compare origin list with decrement sorted list
        Collections.reverse(arrPos);
        for(int i = 0; i < arrPos.size(); i++){
            
            if(revVis[i] || arrPos.get(i).index == i) 
                continue;
            
            int circleLength = 0;
            int j = i;
            while(!revVis[j]){
                revVis[j] = true;
                circleLength ++;
                
                j = arrPos.get(j).index;
            }
            
            if(circleLength > 0) revRes += circleLength - 1;
        }
        
        return Math.min(res, revRes);
    }
}

class Pair{
    int value;
    int index;
    
    Pair(int v, int i){
        value = v;
        index = i;
    }
}