Recently I encountered a problem which is very similar to RMQ.
Abridged Statement : First, you have an empty array. You have two operations :
Insert a value v between positions x - 1 and x (1 ≤ x ≤ k + 1) where k is the current size of the array.(positions are 1-indexed)
Find the maximum in the range [l, r] (i.e. the maximum from the positions l to r inclusive)
There are at most Q ≤ 250000 queries.
My current solution uses SQRT decomposition but it was not fast enough to get AC. I was wondering if there is an 
or 
solution.
