\(X\) を固定して考えます。\(X\) を極大な単調減少列 \(D_1,D_2,\dots,D_k\) に分解します。例えば、\(X = (5,2,6,3,1,4)\) なら \(D_1=(5,2),D_2=(6,3,1),D_3=(4)\) となります。

\(D_i\) の間を跨ぐタイミングしかスコアが増えることはないので、スコアの最大値は \(k-1\) です。また、\(k-1\) になる条件は以下です。

• 各 \(D_i\) から要素を \(1\) 個以上選んでいる。
• 全ての \(i(1 \le i \le k-1)\) において、\(D_i\) から選んだ最小値 \(<\) \(D_{i+1}\) から選んだ最大値が成り立つ。

この条件を満たす部分列を手前から構築していきます。まずは \(D_1\) の最小値を選べばよいです。\(D_x\) の \(y\) を選んだ次に取るべき要素は、以下のように定まります。(証明の都合のため、ある要素を部分列に順番を保ったまま複数回含むことを許容します。例えば、\((x,y,z)\) の部分列として \((x,z,z)\) を選ぶことを許容します。)

• $y > \max(D_{x+1})$ が成り立つとき

次に選ぶべきは $\min(D_x)$ です。$D_{x+1}$ 以降の要素を次に選ぶと $i=x$ の条件を満たせません。$D_x$ の $\min(D_x)$ 以外の要素を選んだ場合、その要素を $\min(D_x)$ に置き換えても条件を満たす部分列が得られます。

• $y \le \max(D_{x+1})$ が成り立つとき

次に選ぶべきは $D_{x+1}$ の要素のうち、$y$ 以上の最小の要素 $z$ です。$D_{x+2}$ 以降の要素を次に選ぶと $i=x$ の条件を満たせません。$D_{x+1}$ から選ぶとすると $y$ 以上の要素を選ぶことになりますが、$z$ 以外を選んだ場合、その要素を $z$ に置き換えても条件を満たす部分列が得られます。$D_x$ から選ぶとすると、$\min(D_x)$ を選ぶのが最善ですが、この次に選ぶ $D_{i+1}$ の要素 $w$ は $z$ を選んだ後にも選べる、もしくは今回選ぶことが出来ます。

この手続きを \(D_k\) の要素を選んでいる状態になるまで繰り返せばよいです。

\((P_l,P_{l+1},\dots,P_r)\) について求める場合も上記と同じことをすればよいです。予め、\(P\) を \(D_1,D_2,\dots,D_k\) に分解しておきます。

\(P_l\) が \(D_i\) に、\(P_r\) が \(D_j\) に属しているとします。\(i = j\) の場合は答えは \(1\) です。\(i < j\) の場合は、\(\min(D_i)\) を選び、上記の手続きを \(D_j\) まで繰り返せばよいです。

\(D_x\) の \(y\) を選んでいるときに次に何を選ぶかは、\(l,r\) に依存しません。よって、予め各要素について今自分を選んでいるときに次にどの要素を選ぶかを求めておき、クエリをダブリングで処理すればよいです。よって \(\mathrm{O}((N+Q) \log N)\) でこの問題を解くことが出来ます。