algorithms – Design a data structure with constant insertion and sublinear range maximum query

Suppose we have access to a stream of ordered pairs, where the $i^{text{th}}$ element in the stream is an ordered pair $(a_i, b_i)$, where $a_i$ and $b_i$ are both arbitrary reals. How can we design a data structure with the following two methods:

  1. $mathcal{O}(1)$ insert
  2. Sublinear lookup to determine when, given some real $a$ as an argument, find the maximum value of $b_i$ for all elements $(a_i, b_i)$ already in our data structure with $a_i$ in the range $(a-1, a)$.

Note: The $a_i$‘s are not necessarily in sorted order in the stream.