<PREV Problem:
NEXT>
Solved by 427 users: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

RMQ problem

Time limit = 5 second(s)

Memory limit = 32000 Kb

You are given large array of real numbers:

a[0], a[1], ..., a[N-1]

Range Minimal Query problem:

Problem RMQ(i,j) = "find minimum of a[i], a[i+1], ..., a[j-1]".

Your program should solve given set of RMQ problems.

Input. Input data has the following format:

N
a[0] a[1] ...   a[N-1]
M
i1 j1
i2 j2
...

iM jM

Here N ≤ 250000, M ≤ 500000, 0 ≤ ik < N, 0 < jkN, ik < jk.

Output. Your program should output M numbers b1, b2, ..., bM delimited by space, where

bk = MIN (a[ik], a[ik + 1], ..., a[jk — 1]).

Input#1
10
1 2 3 4 5 6 7 8 9 10
16
0 1
0 2
0 3
0 4
3 4
3 5
3 6
3 7
3 8
3 9
3 10
0 10
9 10
8 10
7 10
5 6
Output#1
1.000000
1.000000
1.000000
1.000000
4.000000
4.000000
4.000000
4.000000
4.000000
4.000000
4.000000
1.000000
10.000000
9.000000
8.000000
6.000000

Input#2
10
3.86934 7.28362 2.15556 14.75963 0.33240 17.12550 -0.71121 13.90834 -1.13470 5.99831
11
6 10
0 1
5 10
1 9
0 6
0 10
2 5
3 10
5 9
0 8
2 10
Output#2
-1.134700
3.869340
-1.134700
-1.134700
0.332400
-1.134700
0.332400
-1.134700
-1.134700
-0.711210
-1.134700



Author:
Classic problem. Tests and description by Artem Voroztsov.
11 May 2006

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 220ms

SW soft NIX
ID = 54.224.164.166