stack_max_min

Time limit: 0.5s Memory limit: 64MB Input: Output:

Task

You are given NN, an array vv of NN integers indexed from 0, QQ and QQ questions:

  • 1 p1 \ p: What is the greatest ii, i<pi < p for which vi>vpv_i > v_p? If there is no such ii, print −1-1.
  • 2 p2 \ p: What is the greatest ii, i<pi < p for which vi<vpv_i < v_p? If there is no such ii, print −1-1.
  • 3 p3 \ p: What is the smallest ii, i>pi > p for which vi>vpv_i > v_p? If there is no such ii, print nn.
  • 4 p4 \ p: What is the smallest ii, i>pi > p for which vi<vpv_i < v_p? If there is no such ii, print nn.

Input data

The first line contains the integer NN. The second line contains the array vv. The third line contains the integer QQ. The next QQ 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 QQ lines will contain the answers, one line for each answer.

Constraints and clarifications

  • 1≤N≤2â‹…1051 \leq N \leq 2 \cdot 10 ^ 5
  • 1≤Q≤4â‹…N1 \leq Q \leq 4 \cdot N
  • 1≤vi≤1091 \leq v_i \leq 10 ^ 9
  • 0≤p<N0 \leq p < N
# Points Constraints
0 0 Example
1 40 N≤2⋅103N \leq 2 \cdot 10 ^ 3
2 60 No additional constraints

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

Log in or sign up to be able to send submissions!