title: Range minimum queries when array is dynamic
body: <p>I have an array say A(0 indexed) of size 1.</p>
  
  <p>I want to find minimum in array A between indexes k1 (k1>=0) and A.size()-1(i.e the last element). </p>
  
  <p>Then I would insert the value : (minimum element in given range + some "random" constant) at the end of the array.Then I have another query to find minimum between indexes k2 and A.size()-1. I find that, insert the value : (minimum in the given range + another "random" constant) at the end. I have to do many such queries.</p>
  
  <p>Say, I have N queries. Naive approach would take O(N^2). </p>
  
  <p>Cannot use segment trees as array is not static. But, a clever way to do is make segment tree for size N+1 array; beforehand and fill the unknown values with infinity. This would give me O(Nlog N) complexity.</p>
  
  <p>Is there any other method for NlogN complexity or even N?</p>