Yet Another problem

We are given a linear array of n numbers e.g.

1 3 7 2 9 8 5

is a linear array of 7 numbers.

We are given m queries, each of the form:

a b

Basically, 2 integers a and b, a <= b. We want to know between the ath and bth element of the array, what the smallest number is.

For example, if a is 2 and b is 5, the range we are interested in (for the above array) is:

3 7 2 9

since 3 is the 2nd element of the array and 9 is the 5th element.

The answer would be 2, which is the smallest number.

We wish for O(n log n) preprocessing and O(1) query, so that for m queries on n numbers, the time complexity is O(n log n + m). [ I guess O(n^2) preprocessing is REALLY REALLY easy ].

Space required: No more than O(n log n).

Thanks to Ivo and Velin for the solution.