Sparse Table の構築 Step 3 COBOL(Beta)編（paizaランク S 相当）

説明

前回の問題では、任意の長さの区間を 2 つの長さ 2^k の区間で覆う方法を勉強しました。
次に、任意の長さの区間の最小値を、2 つの長さ 2^k の区間の最小値から求めることを目指します。
まずはじめに、各 i について「i から始まる長さ 2^k の区間の最小値」を求めておきます（k は数列の長さを超えないところまで考えるとします）。
「i から始まる長さ 2^k の区間の最小値 （min(A_i, A_{i+1}, ..., A_{i+2^k-1})）」を T_{i,k} と表すことにします。
以下の画像の直線が T_{i,k} の区間を表しています。


例えば、N = 8、A = [4, 2, 5, 6, 1, 3, 7, 8] で区間 [1,7) の最小値を求めることを考えます。
対象となる区間の値は [A_1, A_2, A_3, A_4, A_5, A_6] = [2, 5, 6, 1, 3, 7] です。
前回の問題と同様に考えると、区間 [1,7) は長さ 2^2 = 4 の区間 [1,5) と [3,7) で覆うことができます。
区間 [1,5) の最小値は T_{1,2}、[3,7) の最小値は T_{3,2} であることを思い出すと、
min(A_1, A_2, A_3, A_4, A_5, A_6)
= min(A_1, A_2, A_3, A_4, A_3, A_4, A_5, A_6)
= min(min(A_1, A_2, A_3, A_4), min(A_3, A_4, A_5, A_6))
= min(T_{1,2}, T_{3,2})
と変形でき、2 べきの長さの区間の答えを 2 つ組み合わせることで答えが求められることがわかります。
これは任意の長さの区間に対しても同様に成り立ちます。

なお今回の問題では、T_{i,k} は愚直に計算しても実行制限時間に間に合う制約になっています。

問題

長さ N の数列 A が与えられます。
ここで、数列の要素を 0-index で表すとします。
つまり、数列 A は A_0, A_1, ..., A_{N-1} です。

Q 個のクエリが与えられるので順に解答してください。クエリの形式は以下の通りです。
・l r：数列 A の区間 [l,r) の最小値 min(A_l, A_{l+1}, ..., A_{r-1}) を出力する。