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