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
shrikant1999:
20221011 10:58:19
<snip>


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. 
Added by:  Joshua Kirstein 
Date:  20141018 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 