There is a collection of photos to place into an empty photo album, one at a time by order of importance. Each time a photo is inserted, all subsequent photos are shifted toward right by one position. Given the id’s of the photos and the positions where each should be placed, find out the sequence of the photos in the album after all photos have been inserted.
Example:
n = 5
index = [0, 1, 2, 1 ,2]
identity = [0,1,2,3,4]
*Explanation: *
insert 0 at index 0
insert 1 at index 1
insert 2 at index 2
insert 3 at index 1 and shift 1, 2
insert 4 at index 2 and shift 1, 2
output = [0, 3, 4, 1, 2]
Constraints:
1 <= n <= 2 * 10^5
0 <= indix[i], identity[i] <= n
O(n) solution