Range Minimum Query (Sparse Table) - Classic Problems | Repovive

CLS38. Range Minimum Query (Sparse Table)

2s256 MB

Given an array of $n$ integers and $q$ queries, answer each query asking for the minimum element in the range $[l, r]$ (1-indexed, inclusive).

\begin{array}{l} n \quad q \\ a_1 \quad a_2 \quad \cdots \quad a_n \\ l_1 \quad r_1 \\ \vdots \\ l_q \quad r_q \end{array}

\begin{array}{l} ans_1 \\ ans_2 \\ \vdots \\ ans_q \end{array}

Input

8 3
3 1 4 1 5 9 2 6
1 4
3 7
1 8

Explanation

For this input, the required output is 1 1 1.

Output

1
1
1

Input

Explanation

For this input, the required output is 2 1 1.

Output

2
1
1

Input

6 3
1 2 3 4 5 6
1 3
4 6
2 5

Explanation

For this input, the required output is 1 4 2.

Output

1
4
2

Given an array of $n$ integers and $q$ queries, answer each query asking for the minimum element in the range $[l, r]$ (1-indexed, inclusive).

\begin{array}{l} n \quad q \\ a_1 \quad a_2 \quad \cdots \quad a_n \\ l_1 \quad r_1 \\ \vdots \\ l_q \quad r_q \end{array}

\begin{array}{l} ans_1 \\ ans_2 \\ \vdots \\ ans_q \end{array}