Dynamic Data structure for All nearest smaller values I need a data structure that stores a sequence of numbers and supports the following operations.  The input to each operation includes the position of an item in the current sequence (not the value or the memory address of that item).


$\mathtt{NearestSmaller}(i)$: Return the value of the last item in the sequence that occurs before position $i$ and whose value is less than the value at position $i$.
$\mathtt{InsertBefore}(x, i)$: Insert a new item with value $x$ into the sequence just before the item with position $i$.
$\mathtt{Delete}(i)$: Delete item at position $i$ from the sequence.


In short, my question is whether there is a dynamic version of the all nearest smaller neighbors algorithm.

For example, if the current sequence is $X = [9,7,3,1,8,12,10,20,15,5]$, then 


$\mathtt{NearestSmaller}(6)$ should return $8 = X[5]$, and 
$\mathtt{NearestSmaller}(10)$ should return $1 = X[4]$.
If you modify a balanced binary search tree (whose inorder traversal is the sequence order) so that each node stores the minimum value of its descendants (and if you know the path to x) then you can easily find the nearest smaller value: it must either be on the path to x, or in a left subtree descending from the path. In the first case, you have a logarithmic number of nodes to check, and in the second case you can use the extra information to find the closest left subtree with a value smaller than x and then descend through it along the rightmost path that still has a value smaller than x. So the time per query or update is logarithmic.

Edited to add: Now that you have clarified that you want to identify items in the sequence by their position, you should also augment the search tree so that each node stores its number of descendants. With this information, it is straightforward to find the path to the item at position $i$, in logarithmic time, matching the time described above for the NearestSmaller query.