問題文

長さ$N$の整数列$A$と、そのindexの組$l$,$r$が与えられるので、部分列[$A_l, A_{l+1},\cdots,A_{r-1},A_r$]が
広義単調増加であるか、広義単調減少であるかをそれぞれ判定してください。

回答は、以下で定義される2つの関数$f(l, r), g(l, r)$の値をこの順番で空白区切りで出力することにより行ってください。
\begin{eqnarray} f(l, r)=\left\{ \begin{array}{ll} 1 & (部分列[A_l, A_{l+1},\cdots,A_{r-1},A_r]が広義単調増加である) \\ 0 & (上記以外) \\ \end{array} \right. \end{eqnarray} \begin{eqnarray} g(l, r)=\left\{ \begin{array}{ll} 1 & (部分列[A_l, A_{l+1},\cdots,A_{r-1},A_r]が広義単調減少である) \\ 0 & (上記以外) \\ \end{array} \right. \end{eqnarray}

この問題において、
列$A_0, ... A_k$が広義単調増加であるとは、すべての$0 \leq i < k$について$A_i \leq A_{i+1}$であることを、
列$A_0, ... A_k$が広義単調減少であるとは、すべての$0 \leq i < k$について$A_i \geq A_{i+1}$であることをそれぞれ指します。
ただし、長さ1の部分列は広義単調減少でも広義単調増加でもあるものとします。

なお、indexの組$l$,$r$は$Q$組与えられるので、そのすべてを処理してください。

入力

$N$
$A_0\ \cdots\ A_{N-1}$
$Q$
$l_0\ r_0$
$\vdots$
$l_{Q-1}\ r_{Q-1}$

入力は全て整数で与えられる。

• $1 \leq N \leq 10^5$
• $-10^{18} \leq A_i \leq 10^{18}$
• $1 \leq Q \leq 10^5$
• $0 \leq l_i \leq r_i \leq N-1$

出力

$Q$行出力してください。$i$行目には$f(l_i, r_i),g(l_i, r_i)$を空白区切りで出力して下さい。最後に改行してください。

サンプル

5
8 -3 -4 0 9
3
0 1
1 3
2 4

0 1
0 0
1 0

5
10 10 10 9 9
3
0 0
0 2
2 4

1 1
1 1
0 1

4
-2 0 -2 -3
1
0 3

0 0