Intrinsic Interval in a Permutation

Given a permutation \(\pi\) of integers \(1\) through \(n\), an interval in \(\pi\) is defined as a consecutive subsequence whose sorted order forms a sequence of consecutive integers. More formally, for indices \(a\) and \(b\) where \(1 \le a \le b \le n\), the subsequence \(\pi_a^b = (\pi_a, \pi_{a+1}, \ldots, \pi_b)\) is called an interval if

[ \max(\pi_a,\pi_{a+1}, \ldots,\pi_b) - \min(\pi_a,\pi_{a+1}, \ldots,\pi_b) + 1 = b - a + 1. ]

For a given contiguous subsequence \(\pi_x^y\), its intrinsic interval is defined as any interval \(\pi_a^b\) satisfying \(a \le x \le y \le b\) and having the minimum possible length (i.e. it is as short as possible).

For example, consider \(\pi = (3, 1, 7, 5, 6, 4, 2)\). The subsequence \(\pi_3^6 = (7, 5, 6, 4)\) is already an interval because when sorted it yields \((4, 5, 6, 7)\), a sequence of consecutive integers. In contrast, the subsequence \(\pi_1^3 = (3, 1, 7)\) is not an interval, and its intrinsic interval turns out to be \(\pi_1^7 = (3, 1, 7, 5, 6, 4, 2)\), which is the minimal interval that contains it.

Your task is: Given a permutation \(\pi\) and \(m\) queries (each query gives two indices \(x\) and \(y\) specifying a contiguous subsequence \(\pi_x^y\)), determine one intrinsic interval \(\pi_a^b\) for each query. If the given subsequence is already an interval, then the answer is simply \(a=x\) and \(b=y\). Otherwise, you need to expand the subsequence to the smallest contiguous segment that forms an interval.

inputFormat

The input begins with two integers \(n\) and \(m\) (\(1 \leq n \leq 10^5\), \(1 \leq m \leq 10^5\)) where \(n\) is the size of the permutation and \(m\) is the number of queries.

The next line contains \(n\) distinct integers which represent the permutation \(\pi\) of \(1\) through \(n\).

Each of the following \(m\) lines contains two integers \(x\) and \(y\) (\(1 \leq x \leq y \leq n\)) specifying the boundaries of the query subsequence \(\pi_x^y\).

outputFormat

For each query, output two integers \(a\) and \(b\) (with \(1 \leq a \leq x \leq y \leq b \leq n\)) representing the boundaries of an intrinsic interval that contains the queried subsequence. Each answer should be on a separate line.

sample

7 3
3 1 7 5 6 4 2
3 6
1 3
4 4

3 6
1 7
4 4