Vector to store the left and right index for each i such that left [ i ] > arr [ i ] and right [ i ] > arr [ i ]
int [ ] left = new int [ n ] ; int [ ] right = new int [ n ] ; Stack s = new Stack ( ) ; s . Push ( new Tuple < int , int > ( Int32 . MaxValue , - 1 ) ) ;