問題文

数列 $X=(X_1,\dots,X_k)$ の美しさを次で定義します。

• $(l,r) \ (1 \leq l \leq r \leq k)$ を選び、$X$ の $X_l,\dots,X_r$ を単一の要素 ${\rm Med}(X_l,\dots ,X_r)$ で置き換えた長さ $k+l-r$ の数列 $X'$ を作る。
  $X$ の美しさは、このような $X'$ としてあり得るもの全てを考えたときの ${\rm Med}(X')$ の最小値である。

ここで $Y=(Y_1,\dots,Y_k)$ に対し ${\rm Med}(Y)$ は $Y_1,\dots,Y_k$ の中央値、すなわち $Y_1,\dots,Y_k$ を昇順に並べ替えたときの $\displaystyle \left \lfloor \frac{k}{2} \right \rfloor +1$ 番目の要素を表します。

長さ $N$ の数列 $(A_1,\dots,A_N)$ が与えられます。

次の $Q$ 個のクエリを処理してください。

$l$ $r$

• 数列 $(A_l,\dots,A_r)$ の美しさを出力する。

入力

$N$ $Q$
$A_1$ $\dots$ $A_N$
$l_1$ $r_1$
$\vdots$
$l_Q$ $r_Q$

• 入力は全て整数
• $1 \leq N \leq 5 \times 10^4$
• $1 \leq Q \leq 5 \times 10^4$
• $1 \leq A_i \leq N$
• $1 \leq l_i \leq r_i \leq N$

出力

各クエリに対する解を改行区切りで出力してください。

サンプル

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

2
5
1

3 3
3 3 3
1 3
2 3
3 3

3
3
3

20 10
1 6 6 19 13 10 20 1 8 11 12 4 7 3 10 20 19 13 14 13
1 20
2 13
6 7
5 16
9 13
12 14
11 13
10 13
2 14
6 17

6
6
20
10
7
4
7
7
6
10