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
shanto09: 2020-03-11 14:50:53

AC with sparse table..

chaudhary_19: 2019-09-09 21:49:30

Sparse Table makes your life easier !!!

chirayu_555: 2019-08-19 13:36:07

AC in one go. Easy with segment tree.

necrofool: 2019-07-13 17:55:17

Easy using segment tree. Easier Using Sparse Table:)

akash19jain: 2019-05-19 17:55:44

I tried many times using Segment tree but I am getting WA after the 5th case. Can anyone help me?

aj_254: 2019-04-26 10:33:42

ac in one go python 3.5 just increase recursion limit by sys.setrecursionlimit(15000) and use segment tree

riz1ahmed: 2019-04-26 01:03:05

AC With Square Root Decomposition. Now Try With Segment Tree. And then will try with Sparse TAble.

amantu_amir: 2019-03-30 21:19:06

Easy one,
ac 0.01s using segment tree

Last edit: 2019-03-30 21:19:25
medhruv7: 2019-03-17 08:14:39

fake_death how u did in 0.01s can u send the code

Last edit: 2019-03-17 08:15:05
medhruv7: 2019-03-17 08:12:57

0.03 sec for sparse tree with log optimization :)


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