title: Maintain a sorted array in O(1)?
body: <p>We have a sorted array and we would like to increase the value of one index by only 1 unit (array[i]++), such that the resulting array is still sorted. Is this possible in O(1)? 
  It is fine to use any data structure possible in STL and C++. </p>
  
  <p>In a more specific case, if the array is initialised by all 0 values, and it is always incrementally constructed only by increasing a value of an index by one, is there an O(1) solution?</p>