Minimum and Maximum

You are given N integers in input order, where 1 <= N <= 100,000. Each integer is between 1 and 1,000,000,000 inclusive.

For one interval from the a-th integer through the b-th integer, finding the minimum and maximum is simple. However, M such intervals are given, where 1 <= M <= 100,000. For every interval, find the minimum and maximum among the integers in that input-order range.

Here, the a-th integer means the integer that appeared a-th in the input. For example, if a = 1 and b = 3, consider the first, second, and third integers.

The first line contains N and M.

Each of the next N lines contains one integer.

Each of the next M lines contains a pair a and b.

Print M lines in the order the queries are given. For each pair a and b, print the minimum and then the maximum.