Comment by throwaway_1more

If the value you dropped wasn't the max, no problem, if it was, you recompute over the window. It is amortized.