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 19:23:41

This problem can be solved using segment tree or sparse table algorithm.
In this case, sparse table is more efficient because the array is static and sparse algorithm runs faster.

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