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
darkknight21: 2018-11-06 19:35:48

Sparse Table implementation
So Easy when you learn this DS

suhail_786: 2018-10-25 20:02:12

question is simple, doesn't require any data structure except array.O(m*n) is not bad

davidvc: 2018-10-06 18:54:41

0.04 with union find and cstdio (was 0.10 using iostream--IO seems like it matters more than algorithm)

Last edit: 2018-10-06 18:55:04
sawlani_123: 2018-09-16 13:01:25

0.02s
Using Segment tree
Thanx spoj
Learnt a new topic today

jmr99: 2018-07-16 10:05:46

to solve anyone can learn these topics.
1. Segment Tree
2. Sparse Table
3.Square Root Decomposition

fake_death: 2018-05-29 22:15:47

AC 0.01s using sparse table :D

lamia2658: 2018-05-29 12:08:47

just like water.. range minimum query simply.. :3

elmer_fudd: 2018-05-09 18:57:39

using sqrt decomposition but still run time error.
my code: https://ideone.com/***********************see notes below*************

Please help ..why my code is run time.

or anyone give me the solution of sqrt decomposition please

Last edit: 2018-05-11 08:56:22
m2do: 2018-04-25 17:49:05

1. Sparse Table = 0.09 secs...
2. Square Root Decomposition = 0.10 secs...
3. Segment Tree = 0.03 secs...

Last edit: 2018-04-25 17:49:48
a_h_k_81: 2018-02-26 22:26:29

Last edit: 2018-02-26 22:26:46

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