Vasya vs Rhezo
Tag(s):

## Data Structures, Easy-Medium

Problem
Editorial
Analytics

Queen Vasya is preparing for a war against Rhezo. She has N warriors in total arranged in a line. Let us number the warriors by numbers from 1 to N. She will fight Rhezo's army for Q days, and each day she can choose only one warrior.

For each warrior, we know 2 values associated with him, let us call these A and B. Each day Vasya can choose her warrior from a range $L_i$ to $R_i$, she must choose the warrior with maximum A value. If there is more than 1 warrior having the same maximum A value, she chooses the warrior with minimum B value. If still there is more than 1 warrior with same maximum A value and same minimum B value, she chooses the one with lower index in line.

You being the hand of Queen Vasya, need to help her in choosing the warrior for each day.

Input:

First line contains a single integer N, denoting the number of warriors Queen Vasya has. Second line contains N space separated integers $A_i$. Third line contains N space separated integers $B_i$. Next line contains a single integer Q, denoting the number of days Queen Vasya chooses a warrior. Each of the next Q lines contains 2 integers $L_i$ and $R_i$.

Output:

For each $L_i$ and $R_i$, print the index of the warrior that Queen Vasya should choose.

Constraints:

$1 \le N, Q \le 10^6$

$1 \le A_i, B_i \le 10^9$

$1 \le L_i \le R_i \le N$

SAMPLE INPUT
5
1 8 4 6 8
4 8 6 3 7
4
1 4
2 4
3 4
1 5

SAMPLE OUTPUT
2
2
4
5

Explanation

For the last query, both warrior number 2 and warrior number 5 have the same maximum A value, but we will choose warrior 5 because he has a lower B value.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

Lenskart Java Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
• Basic Programming > Recursion