Let us fix \(X\). We decompose \(X\) into maximal strictly decreasing subsequences \(D_1,D_2,\dots,D_k\). For example, if \(X = (5,2,6,3,1,4)\), then \(D_1=(5,2),D_2=(6,3,1),D_3=(4)\).

The score can only increase at transitions between \(D_i\)’s, so the maximum score is \(k-1\). The conditions for achieving \(k-1\) are as follows.

• At least one element is chosen from each \(D_i\).
• For all \(i\) \((1 \le i \le k-1)\), the minimum value chosen from \(D_i\) \(<\) the maximum value chosen from \(D_{i+1}\).

We construct a subsequence satisfying these conditions from left to right. First, choose the minimum of \(D_1\). When we have chosen \(y\) from \(D_x\), the next element to choose is determined as follows. (For the sake of proof, we allow an element to appear multiple times in the subsequence while preserving order. For example, we allow choosing \((x,z,z)\) as a subsequence of \((x,y,z)\).)

• When $y > \max(D_{x+1})$

The next element to choose is $\min(D_x)$. Choosing any element from $D_{x+1}$ or later next would fail to satisfy the condition for $i=x$. If we choose an element of $D_x$ other than $\min(D_x)$, replacing it with $\min(D_x)$ still gives a valid subsequence.

• When $y \le \max(D_{x+1})$

The next element to choose is the smallest element $z$ in $D_{x+1}$ that is at least $y$. Choosing any element from $D_{x+2}$ or later next would fail to satisfy the condition for $i=x$. If we choose from $D_{x+1}$, we must choose an element at least $y$, but if we choose anything other than $z$, replacing it with $z$ still gives a valid subsequence. If we choose from $D_x$, the best choice is $\min(D_x)$, but the element $w$ of $D_{i+1}$ to choose next is either choosable after choosing $z$ or can be chosen now.

We repeat this procedure until we have chosen an element in \(D_k\).

The same approach applies when computing for \((P_l,P_{l+1},\dots,P_r)\). We precompute the decomposition of \(P\) into \(D_1,D_2,\dots,D_k\).

Suppose \(P_l\) belongs to \(D_i\) and \(P_r\) belongs to \(D_j\). If \(i = j\), the answer is \(1\). If \(i < j\), choose \(\min(D_i)\) and repeat the above procedure up to \(D_j\).

What to choose next when holding \(y\) in \(D_x\) does not depend on \(l,r\). Thus, we precompute for each element what element to choose next, and process queries using binary lifting. This solves the problem in \(\mathrm{O}((N+Q) \log N)\) time.