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

 © acm.mipt DevGroupThe page was generated in 200ms