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
voidpoint11: 2024-05-21 16:34:15

It is a sparse table problem but I solve this using by segment tree. LOL .xd

foxydimj007: 2024-05-16 17:40:25

you need sparse table for this

tauseeb17: 2023-06-18 16:46:56

why o(N*Q) gives A.C in this question.

Simes: 2023-06-09 13:40:44

@noob_: I see what you mean. My previously AC code now gets NZEC. I don't have any access to the test cases, but I've emailed the admins to request they take a look

n00b_: 2023-06-09 07:51:01

@Simes: I think test cases may be changed. Because, I tried with AC code without any change and again my friends also tried with this. But they all are a failure on test 5. We do not share our own codes. They have also different approach. Please check again.

Simes: 2023-06-08 20:58:31

@n00b_: over 8000 ACs, so yeah, it's probably correct. Don't assume your code passes test cases 1-4, unlike some other OJs, SPOJ doesn't stop on the first failure.

n00b_: 2023-06-08 17:47:01

I tried many times using the Segment tree but I am getting WA after the 5th case. Is test case 5 correct?

m15069: 2023-05-29 22:36:45

Why am I getting wrong answer for errichto's code ?

anuragr135: 2023-02-15 19:25:16

segment tree giving the :(

shrikant1999: 2022-10-11 10:58:19

<snip>
[Simes]: no thanks.

Last edit: 2022-10-11 12:32:46

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