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 countSwaps(List<List<Integer>> indexToValueList) {
        int totalSwaps = 0;        
        Map<Integer, Integer>  indexToIndex = new HashMap<>();
        Set<Integer> startPositions = new HashSet<>();
        for (int i = 0; i <  indexToValueList.size(); i++) {
            indexToIndex.put(i,indexToValueList.get(i).get(0) );
        }
        startPositions.addAll(indexToIndex.values());
        int idx = 0;
        while (! startPositions.isEmpty()) {
            int currentSwaps = 0;
            int startPos = idx;
            int nextPos = indexToIndex.get(idx);
            startPositions.remove(startPos);
            int curpos = startPos;
            while (nextPos != startPos) {
                currentSwaps++;
                startPositions.remove(nextPos);
                nextPos = indexToIndex.get(nextPos);
                curpos = nextPos;

            }
            while (! startPositions.contains(idx)) {
                idx++;
                if (idx >= indexToIndex.size()) {
                    break;
                }
            }
            totalSwaps += currentSwaps;
        }
        return totalSwaps;
    }
    
    public static int lilysHomework(List<Integer> arr) {
         
        class SortByValueUp implements Comparator<List<Integer>>  {
        
        @Override
        public int compare(List<Integer> a, List<Integer> b) {
            int va = a.get(1);
            int vb = b.get(1);
            if (va > vb) {
                return 1;
            }
            if (va < vb) {
                return -1;
            }
            return 0;
          }
      }
      
      class SortByValueDown implements Comparator<List<Integer>> {
          
        @Override
        public int compare(List<Integer> a, List<Integer> b) {
            int va = a.get(1);
            int vb = b.get(1);
            if (va < vb) {
                return 1;
            }
            if (va > vb) {
                return -1;
            }
            return 0;  
          }
      }
      
    // Write your code here
        // minimum is sorted.  How many swaps to sort?
        // A sort is a permutation.  After sorting, count number
        // of things not in place.  All others must swap, and
        // swaps can be a cycle, e.g.:  a<->b, b<->c, c<->d, d<->a
        // or a mirror: a<->b.  4 swaps fix 4 in a ring, mirror fixes 2.
        // Hence we count the loops lengths, e.g. swaps.
        List<List<Integer> > indexToValueList1 = new ArrayList<>();
        List<List<Integer> > indexToValueList2 = new ArrayList<>();
        for (int i = 0; i < arr.size(); i++) {
            List<Integer> entry = new ArrayList<>();
            entry.add(i);
            entry.add(arr.get(i));
            indexToValueList1.add(entry);
            indexToValueList2.add(entry);
        }
        Collections.sort(indexToValueList1, new SortByValueUp());
        Collections.sort(indexToValueList2, new SortByValueDown());
        int s1 = countSwaps(indexToValueList1);
        int s2 = countSwaps(indexToValueList2);
        if (s1 < s2) {
            return s1;
        }
        return s2;
    }
}

def lily_internal(a: list[int], reverse: bool=True):
    targets = {n: i for i, n in enumerate(sorted(a, reverse=reverse))}
    swaps = 0
    for i, n in enumerate(a):
        while i != targets[n]:
            # Swap the current value into the correct place.
            a[targets[n]], a[i] = n, a[targets[n]]
            swaps += 1
            n = a[i]
    return swaps

def lilysHomework(a: list[int]):
    # lily_internal() is destructive, so send a copy the first time.
    return min(lily_internal(list(a), False), lily_internal(a, True))

function countSwap(arr, sortedArr) {
    let swapCount = 0
    const visited = []
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === sortedArr[i][0]) {
            visited[i] = true
            continue
        }
        let pCount = 0; // permutations
        let j = i;
        while(!visited[j]) {
            pCount ++
            visited[j] = true
            j = sortedArr[j][1]
        }
        if (pCount > 1) swapCount += pCount - 1  // this math based on Permutation Cycle Decomposition
    }
    
    return swapCount
}
function lilysHomework(arr) {
    // Write your code here
    const pArr = arr.map((e, i) => [e, i]) // add position to arr
    const aSorted = mergeSort(pArr, true) // ascending sorting, you can choose any sort algo
    const dSorted = mergeSort(pArr, false) // descending sorting
    
    let aSwapCount = countSwap(arr, aSorted)
    let dSwapCount = countSwap(arr, dSorted)
    
    return Math.min(aSwapCount, dSwapCount)
}

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;
    }
}