Solved by 427 users: ...
UserDateAttemptTimeCMSC
alt_ua`16 feb 2008`C++904.9252
alt_ua`16 feb 2008`C++1004.6060
abortmozga.ru`26 sep 2010`C++4002.99168
lychees`01 jul 2011`C++4202.00174
hbmhalley`26 jul 2010`C++302.10184
fetetriste`23 nov 2007`C++1002.13186
abortmozga.ru`25 sep 2010`C++2502.78186
abortmozga.ru`25 sep 2010`C++1802.01190
QWE`15 nov 2007`Kylix604.48196
WsemirZ`27 dec 2007`Kylix902.85202
QWE`25 sep 2007`Kylix304.19205
abortmozga.ru`25 sep 2010`C++1702.00206
QWE`25 sep 2007`Kylix204.00207
Vladislav`27 jun 2012`Kylix603.14208
Philip_PV`12 jul 2008`C602.47210
tnndye`12 may 2007`C++502.56213
 C++ 341 Kylix 62 C 33 Java 10
` >  >  >  >  >  >  >  >  >  > `

## 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

 © acm.mipt DevGroupThe page was generated in 180ms