RPLN  Negative Score
Orianna is a great swimmer and she's going to a swimming competition this month and needs your help as she is highly paranoic about the results of the competition.
The competition consists in some sort of evaluations, every judge makes a score and, based on that score and the score of other contestants she will get a score belonging to her results, those scores are final, meaning that will not change in the competition.
Orianna requires this solution with urgency, she is getting evaluated on a lot of ways and she is very worried about her results, so she wants to know what is the worst score from an evaluation A to other evaluation B inclusive.
Input
The first line of the test data will start with an integer T representing the T test cases, then, T cases will follow, each of the cases starts with two integers N and Q, denoting the number of evaluations Orianna had, then, N integers will follow denoting the score on each evaluation, after that, Q queries will begin, each query consist on two integers A and B.
Output
You must output the string “Scenario #i:“, a blank line and then the result of each query, remember, Orianna is interested on the worst score from evaluation A to evaluation B inclusive.
Example
Input: 2 5 3 1 2 3 4 5 1 5 1 3 2 4 5 3 1 2 4 3 5 1 5 1 3 2 4 Output: Scenario #1: 1 1 2 Scenario #2: 5 4 4
Constraints
 1 <= T <= 100
Small input (30%):
 1 <= N <= 1,000
 1 <= Q <= 1,000
 10^9 <= Ni <= 10^9
 1 <= A <= B <= N
Large input (70%):
 1 <= N <= 100,000
 1 <= Q <= 100,000
 10^9 <= Ni <= 10^9
 1 <= A <= B <= N
Solutions rejudged due to weak test cases.
hide comments
gohanssj9:
20160519 21:39:11
So segment tree and fast i/o gives me 0.78s, Any idea on how to reduce this time? 

tanmaysachan:
20160118 13:42:44
just use an unordered_map for the segtree, and ios::sync_with_stdio(0) for fast i/o 

sonupmandal:
20151111 09:55:13
really good problem...


SANDEEP KUMAR:
20150903 22:42:23
Took all array sizes in 10^5,got AC(1.22s) using sparse table and using scanf and printf. 

Luis Manuel Dï¿½az Barï¿½n:
20141017 13:11:52
Solved using RMQ Sparse Table. 

N0VICE:
20140729 15:43:55
first problem solved using segment trees :)


aristofanis:
20131118 18:13:49
@RAHUL, @Krypt Pen, I think that WA is sent after your program is tested is all test cases, so you cannot be sure that it is failing at the 9th test case... 

Gitu:
20130919 06:17:59
The question taught me that (l+r)/2 is calculated slower than (l+r)>>1 

Smit Mehta:
20130830 10:34:57
Use fast I/O for 9th case. 

govihuu:
20130815 03:07:59
same algorithm C++ accepted, python runtime error (NZEC). I think input isn't orderliness. 
Added by:  david_8k 
Date:  20120622 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own Problem used for the RPL contest 