O(n lg n) time algorithm for GTT

Wang2013 proposed an almost O(n lg n) time algorithm. The gap of $\alpha(n)$ can be reduced with a better data structure. The goal is to be able to partition in linear time.

The data structure should maintain a sequence of integers, and support the following operations: max, delete head, delete tail, delete ith

Paper abstact is available from PubMed http://www.ncbi.nlm.nih.gov/pubmed/24277951