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
madhur4127:
20180226 13:45:45
0.01s using sqrt decomposition and segment tree, but 0.02s using sparse table! Last edit: 20180228 16:06:26 

nikolatech:
20180113 00:19:28
[DELETED] Last edit: 20180507 16:41:15 

biswajitk123:
20171219 09:59:38
first sqrt decomposition :) 

code_aim:
20170825 19:03:24
0.01s


lostground97:
20170823 16:36:06
AC in one go 0.3 secs ^_^ SQRT Decomposition Last edit: 20170823 21:51:14 

pratham_1:
20170723 15:49:19
AC in one go took 0.59s , <JAVA>[*_*] :) 

shashank joshi:
20170526 11:21:17
koi btayega ye code kyun wrong answer de rha hai ?


sonu1801:
20170525 15:52:41
this question can be done in 3 ways(i recommend trying all)


avidcoder:
20170411 08:04:09
Dynamic programming approach with N^2 preprocessing using 2D array won't work 

Randomize:
20161115 11:14:47
solved using modified BIT 
Added by:  Joshua Kirstein 
Date:  20141018 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 