Combined data structure for previous- and next-smaller-values

AbstractLet A be a static array storing n elements from a totally ordered set. We present a data structure of optimal size at most nlog2(3+22)+o(n) bits that allows us to answer the following queries on A in constant time, without accessing A: (1) previous smaller value queries, where given an index i, we wish to find the first index to the left of i where A is strictly smaller than at i, and (2) next smaller value queries, which search to the right of i. As an additional bonus, our data structure also allows one to answer a third kind of query: given indices i