Note: Turn the "result" in main into a long long (c++).

For those doing it in c++, I threw long long at everything I found. Including, the main, where lo and behold, the "result" is an int! So ofcs it was not giving the right result for extra long arrays!!!!!!

Here's my solution, modified Fenwick tree:

long long insertionSort(vector<int> arr) {
    long long count = 0, fenSum = 0;
    static vector<int> fenwick(10000001, 0); 
    fill(fenwick.begin(), fenwick.end(), 0);

    for (int n : arr) {
        count += fenSum;
        int idx = n;
        while (idx) {
            count -= fenwick[idx];
            idx -= idx & -idx;
        }

        idx = n;
        while (idx < 10000001) {
            fenwick[idx] += 1;
            idx += idx & -idx;
        }

        fenSum += 1;
    }

    return count;
}

there's a broken test case for Golang, 1. the moves use int32, some test case overflow 2. for several testcase are broken, it expected to have 15 test set but it only have 15, causes error parsing.

import java.util.*;

public class InsertionSortShiftCounter {

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    int queries = Integer.parseInt(scanner.nextLine().trim());
    for (int q = 0; q < queries; q++) {
        int n = Integer.parseInt(scanner.nextLine().trim());
        int[] arr = Arrays.stream(scanner.nextLine().trim().split(" "))
                          .mapToInt(Integer::parseInt)
                          .toArray();

        long shifts = countShifts(arr);
        System.out.println(shifts);
    }

    scanner.close();
}

// Wrapper to count shifts using merge sort
private static long countShifts(int[] arr) {
    int[] temp = new int[arr.length];
    return mergeSortAndCount(arr, temp, 0, arr.length - 1);
}

// Merge sort with inversion count
private static long mergeSortAndCount(int[] arr, int[] temp, int left, int right) {
    long count = 0;
    if (left < right) {
        int mid = (left + right) / 2;

        count += mergeSortAndCount(arr, temp, left, mid);
        count += mergeSortAndCount(arr, temp, mid + 1, right);
        count += mergeAndCount(arr, temp, left, mid, right);
    }
    return count;
}

// Merge two sorted halves and count inversions
private static long mergeAndCount(int[] arr, int[] temp, int left, int mid, int right) {
    long count = 0;
    int i = left, j = mid + 1, k = left;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
            count += (mid - i + 1); // Count shifts
        }
    }

    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];

    System.arraycopy(temp, left, arr, left, right - left + 1);
    return count;
}

}

Pretty easy with modified merge sort.

def insertionSort(arr):
    arr, count = mergeCountInversions(arr)
    return count

def mergeCountInversions(arr):
    if len(arr) < 2:
        return arr, 0

    c = len(arr) // 2

    left, lc = mergeCountInversions(arr[:c])
    right, rc = mergeCountInversions(arr[c:])

    merged = [0] * len(arr)
    count = lc + rc

    lpos = 0
    rpos = 0

    for i in range(len(arr)):
        if lpos == len(left):
            side = 'r'
        elif rpos == len(right):
            side = 'l'
        elif left[lpos] <= right[rpos]:
            side = 'l'
        else:
            side = 'r'

        if side == 'l':
            merged[i] = left[lpos]
            lpos += 1
        else:
            merged[i] = right[rpos]
            rpos += 1
            count += len(left) - lpos

    return merged, count

include

using namespace std;

string ltrim(const string &); string rtrim(const string &); vector split(const string &);

class FenwickTree { public: FenwickTree(long size) : tree(size + 1, 0) {}

void update(long index, long value) {
    while (index < tree.size()) {
        tree[index] += value;
        index += index & -index;
    }
}

long query(long index) {
    long sum = 0;
    while (index > 0) {
        sum += tree[index];
        index -= index & -index;
    }
    return sum;
}

private: vector tree; };

long insertionSort(vector arr) { long shifts = 0; long maxElement = *max_element(arr.begin(), arr.end()); FenwickTree fenwickTree(maxElement);

for (long i = arr.size() - 1; i >= 0; i--) {
    shifts += fenwickTree.query(arr[i] - 1);
    fenwickTree.update(arr[i], 1);
}

return shifts;

}

int main() { ofstream fout(getenv("OUTPUT_PATH"));

string t_temp;
getline(cin, t_temp);

long t = stol(ltrim(rtrim(t_temp)));

for (long t_itr = 0; t_itr < t; t_itr++) {
    string n_temp;
    getline(cin, n_temp);

    long n = stol(ltrim(rtrim(n_temp)));

    string arr_temp_temp;
    getline(cin, arr_temp_temp);

    vector<string> arr_temp = split(rtrim(arr_temp_temp));

    vector<long> arr(n);

    for (long i = 0; i < n; i++) {
        long arr_item = stol(arr_temp[i]);

        arr[i] = arr_item;
    }

    long result = insertionSort(arr);

    fout << result << "\n";
}

fout.close();

return 0;

}

string ltrim(const string &str) { string s(str);

s.erase(
    s.begin(),
    find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))
);

return s;

}

string rtrim(const string &str) { string s(str);

s.erase(
    find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(),
    s.end()
);

return s;

}

vector split(const string &str) { vector tokens;

string::size_type start = 0;
string::size_type end = 0;

while ((end = str.find(" ", start)) != string::npos) {
    tokens.push_back(str.substr(start, end - start));

    start = end + 1;
}

tokens.push_back(str.substr(start));

return tokens;

}