First of all - please change return type to long, some test cases are meant to return number bigger than 32 bits

Second of all - I gave up for last 3 cases remaining xDD Exceeded time limits on them.. I reckon I need to something more with the rotation..

Here is my C++ solution:

long insertionSort(vector arr) {`

long shifts = 0;
int st_tail_idx = 1;

while (st_tail_idx < arr.size()) {

    int elem = arr[st_tail_idx];
    int tmp_shift = 0;
    int breaker_elem = 0;

    int low = 0;
    int high = st_tail_idx;
    while (low <= high) {
        int mid = (low + high) / 2;
        int guess = arr[mid];
        if (guess < elem) {
            low = mid + 1;
        }
        else {
            high = mid - 1;
        }
    }
    breaker_elem = arr[low];

    tmp_shift = st_tail_idx - low;
    int shift_correction = 0;
    if (breaker_elem == elem) {
        while (low + shift_correction < arr.size() - 1 && arr[low + shift_correction] == breaker_elem) {
            shift_correction++;
        }
    }

    tmp_shift -= shift_correction;
    if (tmp_shift > 0) {

        int new_pos = st_tail_idx - tmp_shift;

        int elems_pack = 1;
        if (st_tail_idx < arr.size() - 1) {
            int last_elem = arr[st_tail_idx + 1];
            for (int i = st_tail_idx + 1; i < arr.size(); i++) {

                if (arr[i] < elem || arr[i] >= breaker_elem || arr[i] < last_elem) {
                    break;
                }
                last_elem = arr[i];

                elems_pack++;
            }
        }

        std::rotate(arr.begin() + new_pos, arr.begin() + st_tail_idx, arr.begin() + st_tail_idx + elems_pack);
        shifts += tmp_shift * elems_pack;

        st_tail_idx += elems_pack;
    }
    else {
        st_tail_idx++;
    }
}

return shifts;

} `