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
thomasdo:
20160922 12:35:32
too hard!!!


rohithr31:
20160917 08:44:08
Square root decomposition also works. 

razor123:
20160912 14:11:09
Segment tree faster than sparse table . Compare O(NlogN+Q) with O(N+QlogN). 

gabbar:
20160702 23:14:45
using array instead of a vector resulted in AC from TLE !! Last edit: 20160705 08:46:34 

kartikay singh:
20160627 13:30:07
Sparse Table ... :) 

abhilc:
20160617 21:37:41
Why not sparse tables? AC! 

dhruvprakash:
20160127 09:23:04
easy .accepted in one go.


karthik1997:
20160125 20:38:05
Tried using MO algorithm . BUt gave tle .


off99555:
20151222 21:20:39
I tried solving using both strategies and the result is that segment tree used 0.18 seconds/3.3MB while sparse table algorithm used 0.27 seconds/4.1MB


off99555:
20151222 19:23:41
This problem can be solved using segment tree or sparse table algorithm.

Added by:  Joshua Kirstein 
Date:  20141018 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 