Static Range Minimum

Difficulty: 1600 4000 ms 128 MB

sparse-table

Each query gives L and R and asks for the minimum of a_L..R. There are many queries, so per-query scanning is too slow at the limits.

Input: the first line has N and Q; the second line has N integers; each of the next Q lines has L and R.

Output: Q lines — the range minimum per query.

Constraints:

• 1 ≤ N, Q ≤ 10⁵
• −10⁹ ≤ a_i ≤ 10⁹

Sample Tests

5 2
5 2 4 1 3
1 3
3 5

2
1

1 1
-5
1 1

-5

Read the Editorial