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
off99555: 2015-12-22 12:15:12

Binary indexed tree is for range-sum query bro not min/max query!

Pagan Min: 2015-12-13 08:38:11

try solving using binary indexed tree

joydeepdas123: 2015-08-22 12:13:41

segmentation fault??

ISHPREET: 2015-08-06 12:50:42

i am getting WA .... Can someone please tell what is the mistake my sol...http://ideone.com/7p7Ct8

:.Mohib.:: 2015-07-29 11:23:12

one of the best solution :D
Nice tutorial.... :)

:.Mohib.:: 2015-07-29 11:18:04

Last edit: 2015-07-29 11:23:23

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