Recently I encountered a problem which is very similar to RMQ.

Abridged Statement : First, you have an empty array. You have two operations :

1. 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)

2. 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.

Edit : Forgot to mention that the queries must be answered online (it's actually function call), so offline solutions doesn't work.