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
shrikant1999: 2022-10-11 10:58:19

<snip>
[Simes]: no thanks.

Last edit: 2022-10-11 12:32:46
trumcspkkk6969: 2022-10-02 12:36:25

how to solve it ussing DSU by youssifgamal ?? too difficulty

youssifgamal: 2022-08-18 03:31:44

how could we solve it using DSU?

linhthebest: 2022-05-19 13:03:48

+ Sprase table (0,12s, 11M): <snip>
+ Segment tree (0,13s, 11M): <snip>
[Simes]: No thanks, we don't want links to code.

Last edit: 2022-05-31 18:52:38
wlguedes: 2022-05-11 02:48:15

Also possible to solve using disjoint set union (https://cp-algorithms.com/data_structures/disjoint_set_union.html#arpa)

namvinhkhang: 2021-12-27 12:05:26

i keep getting WA on test 5 and have no ideas whats wrong
Can someone tell me ?
<snip>

[NG]: No code in comments, use forum.

Last edit: 2021-12-28 01:51:56
mr__abhilash: 2021-10-27 14:35:14

good question

shofiqur_052: 2021-10-17 19:13:09

Algo - Segment tree
Time : 0.07 s
Memory : 5.4 M

Much efficient with this algo, for both, time & memory

Last edit: 2021-10-17 19:14:22
amit2808_: 2021-09-10 08:23:01

Yeah exactly Errichto's video on sparse table is excellent. Done with sparse table.

moarvivek: 2021-07-23 15:05:08

Solved using Square Root Decomposition, Segment tree and Sparse Table.


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