All Tracks Data Structures Advanced Data Structures Segment Trees Problem

Spidey Mania Strikes Again
Tag(s):

Easy-Medium

Problem
Editorial
Analytics

ItsmeAbhi and Mrinmay_spidey_mania are applying for BharGanao, a startup which aims to put their skill of making android application to good use. For that they need to answer some tests regarding spider-man. Since none of them are capable of doing this on their own, you need to help them solve these tests and prove that their love for spider-man isn't unfounded . They are given an array of elements for each test case and they need to solve Q queries per test case (Q is different for every test case). For each query, they are given two integers, L and R, for which they need to find the index of the element which has the minimum value between Lth and Rth (both inclusive) index in the array. If more than one element in the range has the minimum value, print the maximum index out of those.

Input:

T, the number of test cases.
For each test case:
The first line contains N, the number of elements in the array The next line contains N elements separated by a space. (A1, A2, A3, A4,........An); The next line contains Q, the number of queries. Each of the next Q lines have two integers, L and R.

Output:

For each query output a single integer k in the new line, L<=k<=R.

Constraints:

1<=T<=10
1<=N<=10^6
0<=Ai<=10^9
1<=Q<=10^5
1<=L<=R<=N

SAMPLE INPUT
1
5
2 3 4 5 2
3
1 4
2 5
3 4
SAMPLE OUTPUT
1
5
3
Explanation

There are 5 elements in the array. {2,3,4,5,2}.
For first query, the elements in range (1,4) are {2,3,4,5}. So the minimum of them is 2 which has index 1. Thus the answer is 1.
For second query, the 2 at index 5 is minimum in the range (2,5), so the answer is 5.
Similarly, for the third query, the 3 at index 3 is minimum in (3,4). So the answer is 3.

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, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications