クエリを先読みして \(O(N\log N+Q\log N)\) 時間で解く方法を説明します。

\(X=(X_1,X_2,\ldots,X_M)\) に対して、\(f(X)\) を \(i=1\) または \(\max(X_1,X_2,\ldots,X_{i-1})<X_i\) を満たす \(i\) の集合として定義します。\(X\) の良さは \(f(X)\) の要素数と一致します。

\(L\) の降順にクエリを処理します。簡単のため \(B_i=(A_i,A_{i+1},\ldots,A_N)\) とします。\(f(B_{N}), f(B_{N-1}),\ldots,f(B_1)\) をうまく管理したいです。

整数の pair を要素とする stack を持ちます。最初 stack には \((A_N,N)\) が入っています。\(i=N-1,\ldots,2,1\) の順に以下を繰り返します。

1. stack の中身が空でなく、stack の一番上の要素の 1 番目の値が \(A_i\) 以下である限り、stack を pop する。
2. stack に \((A_i,i)\) を push する。

\(i=l\) の処理が終わった後に stack に入っている pair の 2 番目の値を読むと \(f(B_l)\) と一致します。さらに、そのような値のうち \(r\) 以下であるものを数えると、\((A_l, A_{l+1}, \ldots, A_r)\) の美しさと一致します。

stack の push/pop が行われる回数はどちらも高々 \(N\) 回です。したがって、Fenwick Tree のような一点加算と区間和が処理できるデータ構造を用いることでこの問題が \(O(N\log N + Q\log N)\) 時間で解けます。