title: Algorithm to find min and max in a given set
body: <p>A large array <code>array[n]</code> of integers is given as input. Two index values are given - <code>start,end</code>. It is desired to <strong>find very quickly</strong> - <code>min &amp; max in the set [start,end]</code> (inclusive) and <code>max in the rest of array</code> (excluding [start,end]).</p>
  
  <p>eg-</p>
  
  <p>array - 3 4 2 2 1 3 12 5 7 9 7 10 1 5 2 3 1 1</p>
  
  <p>start,end - 2,7</p>
  
  <p>min,max in [2,7] -- 1,12</p>
  
  <p>max in rest - 10</p>
  
  <p>I cannot think of anything better than linear. But this is not good enough as <code>n is of order 10^5</code> and the number of such find operations is also of the same order.</p>
  
  <p>Any help would be highly appreciated.</p>