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
akash19jain: 2019-05-19 17:55:44

I tried many times using Segment tree but I am getting WA after the 5th case. Can anyone help me?

aj_254: 2019-04-26 10:33:42

ac in one go python 3.5 just increase recursion limit by sys.setrecursionlimit(15000) and use segment tree

riz1ahmed: 2019-04-26 01:03:05

AC With Square Root Decomposition. Now Try With Segment Tree. And then will try with Sparse TAble.

amantu_amir: 2019-03-30 21:19:06

Easy one,
ac 0.01s using segment tree

Last edit: 2019-03-30 21:19:25
medhruv7: 2019-03-17 08:14:39

fake_death how u did in 0.01s can u send the code

Last edit: 2019-03-17 08:15:05
medhruv7: 2019-03-17 08:12:57

0.03 sec for sparse tree with log optimization :)

saddhu1005: 2019-02-22 19:58:03

In python 3.5 when I'm running my code in ideone or in any other ide it's working perfectly fine but giving runtime error(NZEC) on submission. any suggestions?

darkknight21: 2018-11-06 19:35:48

Sparse Table implementation
So Easy when you learn this DS

suhail_786: 2018-10-25 20:02:12

question is simple, doesn't require any data structure except array.O(m*n) is not bad

davidvc: 2018-10-06 18:54:41

0.04 with union find and cstdio (was 0.10 using iostream--IO seems like it matters more than algorithm)

Last edit: 2018-10-06 18:55:04

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