Static RMQ

AC一覧

問題文

• $l_i$ $r_i$: $\min(a_l, a_{l+1}, ..., a_{r_i - 1})$ を出力する。

制約

• $1 \leq N, Q \leq 500,000$
• $0 \leq a_i \leq 10^9$
• $0 \leq l_i < r_i \leq N$

入力

$N$ $Q$
$a_0$ $a_1$ ... $a_{N - 1}$
$l_1$ $r_1$
$l_2$ $r_2$
:
$l_Q$ $r_Q$


# 1

4 10
2 10 1 100
0 1
0 2
0 3
0 4
1 2
1 3
1 4
2 3
2 4
3 4

2
2
1
1
10
1
1
1
1
100


Timelimit: 5 secs