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
insayn: 2020-08-28 20:55:55

AC with sqrt decomposition!

sksinghl498: 2020-08-06 06:52:38

Bro it's so simple use sparse table .....than u can got the answer

deerawat: 2020-07-30 12:26:14

First question with segment trees!!

syed_tanveer: 2020-07-27 18:47:48

AC 0.04s , segment tree.

i_spidey: 2020-07-23 20:45:15

Done at the first time using segment tree

scolar_fuad: 2020-06-06 20:04:27

solve first if you have learnt RMQ algorithm

flashadarsh: 2020-05-23 12:48:18

Easy using sqrt decomposition :)

raghav_sharma: 2020-05-15 17:05:49

i am using sparse table in python but it is giving tle. Can someone please tell why?

angshuman_03: 2020-04-23 17:50:58

AC using sparse table!

medhruv7: 2020-04-03 00:05:03

AC one go , 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