Sum of LDS

The condition is the whole damn trick:

$$\max(p_i,p_{i+1}) > p_{i+2}.$$

It says every new element is smaller than at least one of the previous two. That makes the LDS much simpler than it looks.

Lemma 1: a descent dominates everything after it

Suppose

$$p_i > p_{i+1}.$$

Then $p_i > p_j$ for every $j>i$.

Proof:

• $p_i > p_{i+1}$ is already true.
• For $j=i+2$, the condition gives

$$p_{i+2} < \max(p_i,p_{i+1}) = p_i.$$

• Now assume $p_{j-1}<p_i$ and $p_{j-2}<p_i$. Then

$$p_j < \max(p_{j-2},p_{j-1}) < p_i.$$

So by induction, once there is a descent at $i$, the value $p_i$ is bigger than everything to its right.

Build a long decreasing subsequence

Look at some subarray $p_l,\dots,p_r$.

Take every position $i$ with

$$l \le i < r \quad \text{and} \quad p_i > p_{i+1},$$

and also take position $r$.

These positions are increasing by index. Their values are decreasing because each chosen descent-start $p_i$ is greater than every later value.

So this is a valid decreasing subsequence of length

$$1 + \#\{i: l \le i < r,\ p_i > p_{i+1}\}.$$

Since every adjacent pair is either an increase or a descent, this is also

$$(r-l+1) - \#\{i: l \le i < r,\ p_i < p_{i+1}\}.$$

So we have a lower bound.

Now prove it is optimal

If $p_i < p_{i+1}$, then no decreasing subsequence can contain both positions $i$ and $i+1$, because the earlier value is smaller. That pair forces us to miss at least one element.

Also, increasing pairs cannot overlap. If both

$$p_i < p_{i+1}$$

and

$$p_{i+1} < p_{i+2}$$

were true, then $p_{i+2}$ would be greater than both previous values, contradicting

$$\max(p_i,p_{i+1}) > p_{i+2}.$$

So all adjacent increasing pairs inside a subarray are disjoint. If a subarray has $A$ adjacent increases and length $m$, any decreasing subsequence misses at least one element from each of those $A$ disjoint pairs. Therefore its length is at most

$$m-A.$$

The lower bound already reached $m-A$, so:

$$\text{LDS}(p_l,\dots,p_r) = (r-l+1) - \#\{i: l \le i < r,\ p_i < p_{i+1}\}.$$

That is the entire problem. No patience sorting, no segment tree, no wizard nonsense.

Summing over all subarrays

First sum the lengths of all subarrays:

$$\sum_{len=1}^{n} len\cdot(n-len+1)=\frac{n(n+1)(n+2)}{6}.$$

Now subtract the contribution of adjacent increases.

For a fixed increasing edge $(i,i+1)$ with $p_i < p_{i+1}$, it appears in exactly the subarrays with

$$l \le i \quad \text{and} \quad r \ge i+1.$$

There are $i$ choices for $l$ and $n-i$ choices for $r$, so this edge is counted in

$$i(n-i)$$

subarrays.

Thus the answer is

$$\frac{n(n+1)(n+2)}{6} - \sum_{i: p_i < p_{i+1}} i(n-i).$$

Complexity

One scan of the array:

$$O(n)$$

per test case, with $O(n)$ memory in this implementation. You can do $O(1)$ memory too, but storing the permutation is clean and easily fits.