Problem Statement

You are given an integer sequence $A$ of length $N$ and a pair of its indices $l$,$r$. Determine whether the subsequence [$A_l, A_{l+1},\cdots,A_{r-1},A_r$] is
monotonically non-decreasing, and whether it is monotonically non-increasing.

Answer by printing the values of the two functions $f(l, r), g(l, r)$ defined below, in this order, separated by a space.
\begin{eqnarray} f(l, r)=\left\{ \begin{array}{ll} 1 & (\text{the subsequence }[A_l, A_{l+1},\cdots,A_{r-1},A_r]\text{ is monotonically non-decreasing}) \\ 0 & (\text{otherwise}) \\ \end{array} \right. \end{eqnarray} \begin{eqnarray} g(l, r)=\left\{ \begin{array}{ll} 1 & (\text{the subsequence }[A_l, A_{l+1},\cdots,A_{r-1},A_r]\text{ is monotonically non-increasing}) \\ 0 & (\text{otherwise}) \\ \end{array} \right. \end{eqnarray}

In this problem,
a sequence $A_0, ... A_k$ is monotonically non-decreasing if $A_i \leq A_{i+1}$ for all $0 \leq i < k$, and
a sequence $A_0, ... A_k$ is monotonically non-increasing if $A_i \geq A_{i+1}$ for all $0 \leq i < k$.
A subsequence of length 1 is considered to be both monotonically non-increasing and monotonically non-decreasing.

There are $Q$ pairs of indices $l$,$r$ given; process all of them.

Input

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

All inputs are integers.

• $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$

Output

Print $Q$ lines. On the $i$-th line, print $f(l_i, r_i),g(l_i, r_i)$ separated by a space. Print a newline at the end.

Sample

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