まずはクエリが \(1\) つのケースを考えます．

入力が \(B=(B_1,\cdots,B_N)\) だとします． まず \(B_m=\max(B)\) とおきます． \(B=XYZ\) と分解するとき，\(B_m\) が \(X,Y,Z\) のいずれに含まれるかで場合分けします．

まず \(Y\) に含まれるケースは簡単です． \(\max(Y)\) は \(B_m\) で確定しているため，\(Y\) を大きくして損しません． よって \(X=(B_1),Y=(B_2,\cdots,B_{N-1}),Z=(B_N)\) のパターンだけ考えればよいとわかります．

次に \(B_m\) が \(X\) に含まれるケースを考えます． 先ほどと同様の考察により，\(Y\) は \(1\) 要素だけを含むとしてよいです． \(Y\) の場所をすべて試せば答えが計算できます．

\(B_m\) が \(Z\) に含まれるケースは \(X\) のケースと同様です． 数列を左右反転すると全く同じコードで解けることになります．

次に複数クエリに答えることを考えます．

\(B_m\) が \(Y\) に含まれるケースは依然として簡単で，単純なRMQです．

\(B_m\) が \(X\) に含まれるケースを処理する方法は，大きく分けて \(2\) つの方針があります．

\(1\) つめの方針は，各 \(Y\) ごとに \(\max (Z)\) を管理する方法です． クエリを \(R_i\) の昇順に処理することにします．\(R_i\) が増えるごとに，各 \(Y\) の \(\max(Z)\) は増大していきます．この増大の様子は区間加算で表すことができるので，区間加算+区間min取得のセグメントツリーを用いることで解くことができます．

\(2\) つめの方針は，各 \(\max(Z)\) ごとに \(Y\) を管理する方針です． \(1\) つめの方針と同様，クエリは \(R_i\) の昇順に処理します． \(\max(Z)\) を取りうる値を stack で管理し，さらにそれについて \(Y\) としてあり得る min の値を管理すれば良いです． これは単純な区間min取得のセグメントツリーで実装できます．

どちらの方針を用いても，計算量は \(O((N+Q) \log N)\) になります．

方針1の回答例(C++)

方針2の回答例(C++)