Let A = (x1, . . . , xn) be an array storing n numbers, and let [a1, b1], . . . , [an, bn] be n intervals with 1 ai bi n, for all 1 i n. Your task is to develop an algorithm which, for every interval [ai, bi], computes the value mi = min{xj | ai j bi}. Note that your algorithm has to compute all values m1, m2, . . . , mn at the same time. The running time of your algorithm should be O(n lg n). Do not analyze your algorithm and do not prove its correctness.