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
trumcspkkk6969:
20221002 12:36:25
how to solve it ussing DSU by youssifgamal ?? too difficulty 

youssifgamal:
20220818 03:31:44
how could we solve it using DSU?


linhthebest:
20220519 13:03:48
+ Sprase table (0,12s, 11M): <snip>


wlguedes:
20220511 02:48:15
Also possible to solve using disjoint set union (https://cpalgorithms.com/data_structures/disjoint_set_union.html#arpa) 

namvinhkhang:
20211227 12:05:26
i keep getting WA on test 5 and have no ideas whats wrong


mr__abhilash:
20211027 14:35:14
good question 

shofiqur_052:
20211017 19:13:09
Algo  Segment tree


amit2808_:
20210910 08:23:01
Yeah exactly Errichto's video on sparse table is excellent. Done with sparse table. 

moarvivek:
20210723 15:05:08
Solved using Square Root Decomposition, Segment tree and Sparse Table. 

sayang992:
20210603 05:52:01
0.13 sec using sparse table and 0.07 using segment tree. Using segment tree gives better result as Q<N here. Although answering query takes O(1) in sparse table but building it takes o(nlog(n)) so overal complexity is O(nlog(n) +Q) for sparse table. But for segment tree building the tree takes O(4n) and answering each query takes O(log(n)) so overall O(n+Qlog(n)). Since Q<N so segment tree gives better time. And for space no doubt segment tree is better as it takes linear space. So my sparse table took 13 MB and segment tree only 5.3 MB. So better use segment tree if query<Size of array.

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