Dekel Tsur

We study the problem of storing the minimum number of bits required to answer next/previous larger/smaller value queries on an array A of n numbers, without storing A. We show that these queries can be answered by storing at most 3.701n bits (the time for answering queries is O(n)). Our result improves the result of Jo and Satti (2016) [12] that gives an upper bound of 4.088n bits for this problem.