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;

}

The template is ****!

First off it suggests that the results will fit in an int.

Secondly my code was too slow due to the large input. Then I modified their io template even further with ios::sync_with_stdio(true) and cin.tie(0) et voila Accepted.

Solved this by using binary indexed tree

class FenwickTree { public: vector tree; long size;

FenwickTree(long n) {
    size = n + 2;
    tree.resize(size, 0);
}

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

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

long queryRange(long left, long right) {
    return query(right) - query(left - 1);
}

};

long insertionSort(vector arr) { long n = arr.size(); vector sorted = arr;

// Coordinate compression
sort(sorted.begin(), sorted.end());
sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());

unordered_map<long, long> compress;
for (long i = 0; i < sorted.size(); ++i) {
    compress[sorted[i]] = i + 1; // 1-based indexing
}

FenwickTree bit(sorted.size());
long shifts = 0;

for (long i = 0; i < n; ++i) {
    long idx = compress[arr[i]];
    // Count number of elements already in BIT that are greater than arr[i]
    shifts += bit.queryRange(idx + 1, sorted.size());
    bit.update(idx, 1);
}

return shifts;

}