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
grapo_oranges: 2021-01-22 07:48:05

ATTENTION! following test case is missing, my code got AC here, but fails on this one!
Input:
2
3 5
1
0 1
Output:
3

amantu_amir: 2021-01-08 15:34:10

AC with Sparse Table.

th3rd_br0: 2020-12-20 13:35:06

This is the problem where sparse table shines! (0.06s)
others possible ds -> segtree, BIT, mo's

Last edit: 2020-12-20 13:35:25
nagpur: 2020-12-06 01:15:14

@nikhil_33 the range is already in 0 index format, u must be decrementing , also increment l and r for 0 index and later decrement.

ritikagarwal47: 2020-11-22 12:54:38

simple using sqrt decomposition!

neerav_1: 2020-11-17 15:08:33

i am getting tle using seg tree..

nikhil_33: 2020-10-07 21:39:57

I am using sparse table and getting wrong answer after 5th case. Can anyone help me?

Last edit: 2020-10-07 21:47:27
shahil198: 2020-09-12 09:01:52

using mo's algo its become very easy ..

fuadul_hasan: 2020-09-12 03:37:46

pure segment tree ... very nice problem.

paliya_64: 2020-09-01 15:10:46

not sure why but ,it even accepted my naive's solution, which I guessed to show TLE, xp


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