Task

You are given $N$, an array $v$ of $N$ integers indexed from 0, $Q$ and $Q$ questions:

• $1 \ p$: What is the greatest $i$, $i < p$ for which $v_i > v_p$? If there is no such $i$, print $-1$.
• $2 \ p$: What is the greatest $i$, $i < p$ for which $v_i < v_p$? If there is no such $i$, print $-1$.
• $3 \ p$: What is the smallest $i$, $i > p$ for which $v_i > v_p$? If there is no such $i$, print $n$.
• $4 \ p$: What is the smallest $i$, $i > p$ for which $v_i < v_p$? If there is no such $i$, print $n$.

Input data

The first line contains the integer $N$. The second line contains the array $v$. The third line contains the integer $Q$. The next $Q$ lines contain the questions.

Because of the large input size, it is recommended to add these lines of code at the beginning of the main() function:

ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

Output data

The first $Q$ lines will contain the answers, one line for each answer.

Constraints and clarifications

• $1 \leq N \leq 2 \cdot 10 ^ 5$
• $1 \leq Q \leq 4 \cdot N$
• $1 \leq v_i \leq 10 ^ 9$
• $0 \leq p < N$

Example

stdin

10
1 2 3 6 4 5 3 2 1 10
12
1 5
2 2
3 9
4 4
1 3
2 4
3 3
4 8
1 9
2 8
3 6
4 7

stdout

3
1
10
6
-1
2
9
10
-1
-1
9
8