Retroactive deque described in this paper http://erikdemaine.org/papers/Retroactive_TALG/, impelmented on top of a range B-tree, works in O(log n) per operation where n is the numeber of oprations.
Tester is also implemented creates random test examples, calculates the desired outputs, and compares them to the output of the retroactive deque. Naturally, the tester is a naive implementation of a retroactive deque and works in O(n) per operation.
-Kliment