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
pratham_1: 2017-07-23 15:49:19

AC in one go took 0.59s , <JAVA>[*_*] :)

shashank joshi: 2017-05-26 11:21:17

koi btayega ye code kyun wrong answer de rha hai ?

<1. Don't post any source code here.>

Last edit: 2017-05-26 12:19:42
sonu1801: 2017-05-25 15:52:41

this question can be done in 3 ways(i recommend trying all)
1.square root decomposition(mo's algorithm).(O(n*sqrt(n))
2.sparse table.(O(n)
3.segment tree.O(nlogn).

avidcoder: 2017-04-11 08:04:09

Dynamic programming approach with N^2 preprocessing using 2D array won't work

Randomize: 2016-11-15 11:14:47

solved using modified BIT

thomasdo: 2016-09-22 12:35:32

too hard!!!

Last edit: 2016-09-22 12:44:19
rohithr31: 2016-09-17 08:44:08

Square root decomposition also works.

razor123: 2016-09-12 14:11:09

Segment tree faster than sparse table . Compare O(NlogN+Q) with O(N+QlogN).

gabbar: 2016-07-02 23:14:45

using array instead of a vector resulted in AC from TLE !!

Last edit: 2016-07-05 08:46:34
kartikay singh: 2016-06-27 13:30:07

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