How to find a segment inside an array so that the l and r are not equal to the min or max with the lowest possible time complexity?

the numbers are from 0 up to 1e9 and n is from from 1 up to 2*1e5

My strategy is to make a two vector of vectors, saving the numbers sorted from index 0 up to i so you can always know the smallest and biggest member of each subarray and then just do a sliding window algorithm.