c++ - How to find maximum(or minimum) in any subarray(of any size) in a given array? -

we given array , queries. each query contains 2 numbers i , j. need find maximum(or minimum) element in subarray starting index i , ending @ index j in given array.

for eg.

arr = [2 , 3 , 5,  8 , 4 , 9] 

and

query 1: (2 , 4) 

the subarray corresponding query [5 , 8 , 4]. so, maximum 8.

note: number of queries 10^5 , there 10^6 elements in array. time limit execution of program 1s . so, guess solution needed has complexity of o(log n) or less per query, n number of elements in array.

counter = i-1 max = min_integer min = max_integer while counter < j:   if arr[counter] > max:     max = arr[counter]   if arr[counter] < min:     min = arr[counter]   counter++ return max,min 

edit:

alternatively, insert maxheap , minheap (o(n)), , thereafter queries o(1).