Construct four auxiliary vectors of size n and initialize them by - 1
vector < int > leftMin ( n , -1 ) ; vector < int > rightMin ( n , -1 ) ; vector < int > leftMax ( n , -1 ) ; vector < int > rightMax ( n , -1 ) ;