Insertion Sort

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

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

    public static int insertionSort(List<Integer> arr) {
    // Write your code here
    int result = 0;

    int[] cumulative = new int[arr.size()];

    int current;
    int shifts;
    int compare;

    for (int i = 1; i < arr.size(); i++) {
        current = arr.get(i);
        shifts = 0;
        for (int j = i-1; j >= 0; j--) {
            compare = arr.get(j);
            if (compare > current) {
                if (compare == current + 1) {
                    shifts += cumulative[j] + 1;
                    break;
                }
                shifts++;
            } else if (compare == current) {
                shifts += cumulative[j];
                break;
            }
        }
        cumulative[i] = shifts;
        result += shifts;
    }

    //System.out.println(Arrays.toString(cumulative));
    return result;
    int result = 0;

    List<Integer> sorted = new ArrayList<>(arr);
    Collections.sort(sorted);

    int[] occurrences = new int[sorted.get(sorted.size()-1)+1];

    for (Integer i : sorted) {
        occurrences[i]++;
    }

    /*LinkedList<Integer> sorted = arr.stream()
                                    .distinct().sorted()
                                    .collect(Collectors.toCollection(LinkedList::new));*/

    /*Map<Integer,Integer> occurences =
        sorted.stream().distinct()
        .collect(Collectors.toMap(i -> i, i -> 0));*/

    /*Map<Integer,List<Integer>> indexes =
        sorted.stream().distinct()
        .collect(Collectors.toMap(i -> i, i -> new ArrayList<>()));*/

    int index = 0;
    int min = nextMin(occurrences, 0);

    /*for (Integer i : sorted) {
        indexes.get(i).add(index);
        index++;
    }*/

    /*for (Integer i : arr) {
        compareIndex = indexes.get(i).get(0);
        if (index > compareIndex) {
            result += index - compareIndex;
        }
        index++;
        indexes.get(i).remove(0);
    }*/

    /*for (Integer i : arr) {
        compareIndex = indexes.get(i).get(0);
        if (index > compareIndex) {
            result += index - compareIndex;
        } else {
            result -= compareIndex - index;
            try {
               result += arr.subList(index + 1, arr.size())
                            .stream().filter(e -> e < i).count();
            } catch (IndexOutOfBoundsException e) {
                break;
            }
        }
        index++;
        indexes.get(i).remove(0);
    }*/

    for (Integer i : arr) {
        System.out.println(min);
        if (i == min) {
            occurrences[i]--;
            if (occurrences[min] == 0) {
                min = nextMin(occurrences, min);
            }
            continue;
        }

        occurrences[i]--;
        /*if (occurrences[min] == 0) {
            min = nextMin(occurrences, min);
        }*/

        try {
            result += arr.stream().skip(index+1).filter(e -> e < i).count();
        } catch (IndexOutOfBoundsException e) {

        }
        index++;
    }

    /*for (int i = 0; i < arr.size() - 1; i++) {
        final int current = arr.get(i);
        result += arr.stream().skip(i+1).filter(e -> e < current).count();
    }*/

    return result;

    }

    public static int nextMin(int[] occurrences, int start) {
        for (int i = start; i < occurrences.length; i++) {
            if (occurrences[i] > 0) {
                return i;
            }
        }
        return -1;
    }

}



public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int t = Integer.parseInt(bufferedReader.readLine().trim());

        IntStream.range(0, t).forEach(tItr -> {
            try {
                int n = Integer.parseInt(bufferedReader.readLine().trim());

                List<Integer> arr = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
                    .map(Integer::parseInt)
                    .collect(toList());

                int result = Result.insertionSort(arr);

                bufferedWriter.write(String.valueOf(result));
                bufferedWriter.newLine();
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        });

        bufferedReader.close();
        bufferedWriter.close();
    }
}