Nediam Number

Given a permutation \(p_1, p_2, \ldots, p_n\) and \(m\) queries, you are to answer each query regarding the nediam number of a subarray of the permutation.

For an array \(a\) of distinct positive integers of length \(|a| \ge 3\), the function \(f(a)\), called the nediam number, is defined recursively as follows:

• If \(|a| = 3\), then \(f(a)\) is the median of \(a\), i.e. the second smallest element (in \(\LaTeX\): \(\mathrm{median}(a)\)).
• If \(|a| > 3\), then for any contiguous segment of length 3 in \(a\), say \([a_i, a_{i+1}, a_{i+2}]\) with median \(x\) (when sorted in increasing order), remove \(x\) from \(a\) to form a new sequence \(b\). Then \(f(a)\) is defined as the maximum among all possible \(f(b)\) values over all valid contiguous segments.

It can be proven that for any valid array \(a\), the optimal strategy always results in \(f(a)\) being the second largest element in \(a\). With this observation, the problem reduces to finding the second largest element in the given subarray.

Your task is to process \(m\) queries where each query gives two indices \(l\) and \(r\) (with \(r-l+1 \ge 3\)). For each query, output the nediam number of the subarray \([p_l, p_{l+1}, \ldots, p_r]\), which is simply the second largest element in that segment.

inputFormat

The first line contains two integers \(n\) and \(m\) (with \(n \ge 3\)) representing the size of the permutation and the number of queries.

The second line contains \(n\) distinct integers which form a permutation of \(1\) to \(n\).

Each of the next \(m\) lines contains two integers \(l\) and \(r\) (with \(1 \le l < r \le n\) and \(r-l+1 \ge 3\)), representing a query.

outputFormat

For each query, output a single integer: the nediam number of the subarray \([p_l, p_{l+1}, \ldots, p_r]\), which is the second largest element in that subarray.

sample

5 3
1 5 2 4 3
1 3
2 5
1 5

2
4
4