There is a O(NlogN) solution with segment tree.

Hi, I had an idea, but I am terrible at implementation, so can you help ensuring if my approach will be correct? or Is there any valid similar approach?

01. In the tree we will take a cnt variable where we will save how many items we have removed so far till the current position.
02. While removing an item from position pos we will increase the cnt value by 1 from pos to end position.
03. In the array we will always save value in their previous position(1 based index).
04. For example let the array is A[] = {2,3,4,5,6}
05. The cnt value in the tree is cnt[] = {0,0,0,0,0}
06. If the query is (c,2) cnt[2] = 0; So we will print A[2+0] which is 3.Update from (2+0) to End by increasyng cnt value by 1 and set A[2+0] = -1.
07. Now A[] = {2,-1,4,5,6} and cnt[] = {0,1,1,1,1}
08. If the query is (a,5) we add this to the end of array.
09. Now A[] = {2,-1,4,5,6,5} and cnt[] = {0,1,1,1,1,1}
10. If the query is (c,3) cnt[3] = 1; So we will print A[3+1] which is 5.Update from (3+1) to End by increasyng cnt value by 1 and set A[3+1] = -1.
11. Now A[] = {2,-1,4,-1,6,5} and cnt[] = {0,1,1,2,2,2}

Thanks!