Recover an array from its insertion indices
Prelimiaries

You can augment an AVL tree to support all the usual operations plus the following:


  Shift$(a,b)$ increases all keys $k \ge a$ by $b \ge 0$ in $O(\log n)$ time (where $n$ is the number of elements in the tree).


To do so add a value $x_v$ to each node $v$ in the tree. This value represents an offset to be added to all keys stored in the subtree rooted at $v$. The Search, Insert, and Shift operations, along with the required rotations can be implemented as follows (I won't be using the Delete operation, but it can also be implemented). 

Search
The search operation work as usual except that you now keep track of the cumulative offset in the path from the current node to the root.

Insert
To insert a node with key $k$, use the search operation to find the position where a node with key $k$ would need to be placed and the cumulative offset $\overline{x}$ up to that point. Add a leaf in that position and store its key as $k - \overline{x}$. Perform the necessary rotations to rebalance the tree (see the sequel).

Rotations To perform a right rotation on $u$ let $v$ be its left child. 
"Push down" the offset of $u$ as follows: increment the stored key of $u$ by $x_u$, add $x_u$ to the offsets of the children of $u$, and set $x_u$ to $0$. Similarly, "push down" the offset of $v$. Perform the rotation as usual. Left rotations are symmetric.

Shift$(a,b)$. Find the node $u$ with key $a$ or, if no such node exists, find its successor (if the successor doesn't exist either, we are done). Increase the stored key of $u$ by $b$. If $u$ has a right child $v$ then increase $x_v$ by $b$ as well. Walk from $u$ to the root of the tree. Every time you walk to a vertex $w$ from its left child, increase the key of $w$ by $b$ and the offset $x_z$ of the right child $z$ of $w$ by $b$ (if $z$ exists).



Solving your problem

Keep an augmented AVL tree $T$ and consider the operations one at a time. At the end of the generic $i$-th step, the tree will contain $i$ nodes that collectively store the elements of the first $i$ operations. 
Each node $u$ is associated with one element of the array. The key of $u$ is exactly the position of $u$'s element in the array, as of the $i$-th operation, while the element's value is stored as satellite data in $u$.

When the operation $(a_i, z_i)$ is to be processed do a Shift$(z_i, 1)$ operation on $T$. Then, insert a new node with key $z_i$ and satellite data $a_i$ in $T$.

At the end of the process you can traverse the tree and recover the final position (the node's key) of each array element (the node's satellite data). 

The total time required is $O(n \log n)$.