RMQSQ  Range Minimum Query
You are given a list of N numbers and Q queries. Each query is specified by two numbers i and j; the answer to each query is the minimum number between the range [i, j] (inclusive).
Note: the query ranges are specified using 0based indexing.
Input
The first line contains N, the number of integers in our list (N <= 100,000). The next line holds N numbers that are guaranteed to fit inside an integer. Following the list is a number Q (Q <= 10,000). The next Q lines each contain two numbers i and j which specify a query you must answer (0 <= i, j <= N1).
Output
For each query, output the answer to that query on its own line in the order the queries were made.
Example
Input: 3
1 4 1
2
1 1
1 2 Output: 4
1
hide comments
grapo_oranges:
20210122 07:48:05
ATTENTION! following test case is missing, my code got AC here, but fails on this one!


amantu_amir:
20210108 15:34:10
AC with Sparse Table. 

th3rd_br0:
20201220 13:35:06
This is the problem where sparse table shines! (0.06s)


nagpur:
20201206 01:15:14
@nikhil_33 the range is already in 0 index format, u must be decrementing , also increment l and r for 0 index and later decrement. 

ritikagarwal47:
20201122 12:54:38
simple using sqrt decomposition! 

neerav_1:
20201117 15:08:33
i am getting tle using seg tree..


nikhil_33:
20201007 21:39:57
I am using sparse table and getting wrong answer after 5th case. Can anyone help me? Last edit: 20201007 21:47:27 

shahil198:
20200912 09:01:52
using mo's algo its become very easy .. 

fuadul_hasan:
20200912 03:37:46
pure segment tree ... very nice problem. 

paliya_64:
20200901 15:10:46
not sure why but ,it even accepted my naive's solution, which I guessed to show TLE, xp 
Added by:  Joshua Kirstein 
Date:  20141018 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 