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
cooli0_1:
20210513 18:30:10
O(nlgn) preprocessing and O(1) query time using sparse Table :D 

rushi2001:
20210513 14:43:40
Tried in 3 Ways .


nrgshrivastava:
20210426 07:34:17
Those getting wrong answer at case 5 using SQRT decomposition just check if the left and right query both belongs to same block or not.


amz42:
20210420 17:17:48
I tried solving it using square root decomposition & got Wrong Answer. Pls tell me where I'm wrong.


loser_404:
20210420 12:55:43
Anyone is struggling in this problem should watch Erricto's video. Much more detailed way of explanation using Sparse Table 

rds_98:
20210418 22:06:59
An easy and basic known problem in segment tree or sparse table. 

sahil__bajaj:
20210408 11:04:10
I am getting TLE with segment tree Last edit: 20210408 11:05:38 

teknath64:
20210402 11:52:51
square root decomposition in 0.15s 

parvejmia:
20210324 08:08:17
Solved it using Centroid Decomposition in 0.88s 

sam_saver_23:
20210302 16:22:46
I'm trying to do it using sqrt decomposition but getting SIGSEGV runtime error. But the sample test cases are working just fine. Can someone please help? 
Added by:  Joshua Kirstein 
Date:  20141018 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 