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
darkknight21:
20181106 19:35:48
Sparse Table implementation


suhail_786:
20181025 20:02:12
question is simple, doesn't require any data structure except array.O(m*n) is not bad 

davidvc:
20181006 18:54:41
0.04 with union find and cstdio (was 0.10 using iostreamIO seems like it matters more than algorithm) Last edit: 20181006 18:55:04 

sawlani_123:
20180916 13:01:25
0.02s


jmr99:
20180716 10:05:46
to solve anyone can learn these topics.


fake_death:
20180529 22:15:47
AC 0.01s using sparse table :D 

lamia2658:
20180529 12:08:47
just like water.. range minimum query simply.. :3


elmer_fudd:
20180509 18:57:39
using sqrt decomposition but still run time error.


m2do:
20180425 17:49:05
1. Sparse Table = 0.09 secs...


a_h_k_81:
20180226 22:26:29
Last edit: 20180226 22:26:46 
Added by:  Joshua Kirstein 
Date:  20141018 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 