title: Efficiently convert array to cartesian tree
body: <p>I know how to convert an array to a cartesian tree in O(n) time</p>
  
  <ol>
  <li><a href="http://en.wikipedia.org/wiki/Cartesian_tree#Efficient_construction" rel="nofollow">http://en.wikipedia.org/wiki/Cartesian_tree#Efficient_construction</a> and</li>
  <li><a href="http://community.topcoder.com/tc?module=Static&amp;d1=tutorials&amp;d2=lowestCommonAncestor#From" rel="nofollow">http://community.topcoder.com/tc?module=Static&amp;d1=tutorials&amp;d2=lowestCommonAncestor#From</a> RMQ to LCA</li>
  </ol>
  
  <p>However, the amount of memory required is too high (constants) since I need to associate a left and right pointer at least with every node in the cartesian tree.</p>
  
  <p>Can anyone link me to work done to reduce these constants (hopefully to 1)?</p>