Given an array of elements, along with their insertion position. Find the final array.

Basically, we're supposed to shift the elements by 1 if there's an element already at that index.

Example:
arr = {1, 2, 3, 4, 5}
index = {0, 1, 2, 1, 2}

Output = {1,4,5,2,3}

Sequence:

1 inserted at index 0 -> {1}
2 inserted at index 1 -> {1,2}
3 inserted at index 2 -> {1,2,3}
4 inserted at index 1, elements shifted -> {1,4,2,3}
5 inserted at index 2, elements shifted -> {1,4,5,2,3}

size of arr = 10^5 (Bruteforce timedout for some tests.)