\(P\) を十分に大きい素数とし，\(r\) を \(\{0,1,\dots,P-1\}\) から一様ランダムに選びます．

区間 \([L,R]\) に対し，\(h(L,R) := \displaystyle\sum_{i \in [L,R], A_i = \max\{A_L, A_{L+1}, \dots, A_i\}} r^i \bmod P\) と定め，\(h(L_{i,1},R_{i,1}) r^{-L_{i,1}} = h(L_{i,2},R_{i,2})r^{-L_{i,2}}\) が成り立つならば Yes，成り立たないならば No と判定することを考えます．両辺は \(r\) の高々 \(N\) 次の多項式であり，\((A_{L_{i,1}}, A_{L_{i,1} + 1}, \dots, A_{R_{i,1}})\) と \((A_{L_{i,2}}, A_{L_{i,2} + 1}, \dots, A_{R_{i,2}})\) が似ているとき，またそのときのみ両辺の多項式が一致するため，Schwartz–Zippel lemma により，各 \(i\) に対し判定を誤る確率は高々 \(\displaystyle \frac{N}{P}\) となります．よって，\(Q\) 個のクエリのうち \(1\) つ以上に対し誤答する確率は高々 \(\displaystyle \frac{NQ}{P}\) となります．

\(h(L,R)\) を高速に計算する方法を考えます．\(A_0 = \infty\) とおき，\(i = 1, 2, \dots, N\) について \(l_i := \min\{j \mid A_j > A_i\} + 1, r_i := i\) とおくと，\(h(L,R) = \displaystyle \sum_{i \in [L,R], L \in [l_i,r_i]} r^i \bmod P\) が成り立ちます．\(B_{L,i} := \begin{cases} r^i \bmod P & (L \in [l_i,r_i]) \\ 0 & (L \notin [l_i,r_i]) \end{cases}\) とおくと，\(h(L,R) = \displaystyle \sum_{i \in [L,R]}B_{L,i}\) となります．\(L = N, N-1, \dots, 1\) の順に \(B_{L,i}\) を求め，各クエリに対し適切な時点での区間和を計算することで，\(h(L,R)\) を求めることができ，これらの操作は Binary Indexed Tree を用いることで高速に行うことができます．

時間計算量は \(O((N+Q)\log N)\) となります．