how did you inforce the requirements given in q4, I understand the inversions added due to relative ordering? I feel the prefix of permutation changes when adding elements so not sure how you are handling that.
Yes, the prefix of permutation changes, but the relative ordering of the prefix does not change - and the number of inversions of any prefix is only dependent on the relative ordering of the elements