RMQSQ - Range Minimum Query

no tags 

You are given a list of numbers and queries. Each query is specified by two numbers and j; the answer to each query is the minimum number between the range [i, j] (inclusive).

Note: the query ranges are specified using 0-based 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 <= 10,000). The next Q lines each contain two numbers i and which specify a query you must answer (0 <= i, j <= N-1).

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
cooli0_1: 2021-05-13 18:30:10

O(nlgn) preprocessing and O(1) query time using sparse Table :D

rushi2001: 2021-05-13 14:43:40

Tried in 3 Ways .
Way Used :
1> Segment Tree - 0.09
2> Sparse Table - 0.13
3> Square-root Decomposition - 0.07

Last edit: 2021-06-27 20:55:08
nrgshrivastava: 2021-04-26 07:34:17

Those getting wrong answer at case 5 using SQRT decomposition just check if the left and right query both belongs to same block or not.
If they belong to same block just travel linearly in the given array from L to R else you can go with SQRT decomposition.

Last edit: 2021-04-26 07:35:13
amz42: 2021-04-20 17:17:48

I tried solving it using square root decomposition & got Wrong Answer. Pls tell me where I'm wrong.
link: <snip>
[Simes]: Please use the forum for this.

Last edit: 2022-06-01 07:38:17
loser_404: 2021-04-20 12:55:43

Anyone is struggling in this problem should watch Erricto's video. Much more detailed way of explanation using Sparse Table

rds_98: 2021-04-18 22:06:59

An easy and basic known problem in segment tree or sparse table.

sahil__bajaj: 2021-04-08 11:04:10

I am getting TLE with segment tree

Last edit: 2021-04-08 11:05:38
teknath64: 2021-04-02 11:52:51

square root decomposition in 0.15s

parvejmia: 2021-03-24 08:08:17

Solved it using Centroid Decomposition in 0.88s

sam_saver_23: 2021-03-02 16:22:46

I'm trying to do it using sqrt decomposition but getting SIGSEGV runtime error. But the sample test cases are working just fine. Can someone please help?


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