Let 𝑖1,…,𝑖𝑚
be the set of 𝑖∈[1,𝑛]
such that 𝑎𝑖>𝑎𝑖+1
. Let us show that the sequence (𝑖1,…,𝑖𝑚)
is an LDS:

It is a decreasing subsequence: let 𝑘∈[1,𝑚−1]
. If 𝑖𝑘+1=𝑖𝑘+1
, then 𝑎𝑖𝑘>𝑎(𝑖𝑘)+1=𝑎𝑖𝑘+1
. Else, we have 𝑎(𝑖𝑘)+2<max(𝑎𝑖𝑘,𝑎(𝑖𝑘)+1)
, but 𝑖𝑘+1
is such that 𝑎𝑖𝑘+2≥𝑎𝑖𝑘+1
, so 𝑎(𝑖𝑘)+2<𝑎𝑖𝑘
. We have also 𝑎𝑖𝑘+1<𝑎𝑖𝑘
by definition so we can easily prove by induction on 𝑗>0
that 𝑎𝑖𝑘+𝑗<𝑎𝑖𝑘
where it makes sense.
It's optimal : let 𝐸
be the set of indexes taken by a LDS. For each i such that 𝑎𝑖≤𝑎𝑖+1
, at least one of the elements of 𝑖,𝑖+1
does not belong to 𝐸
. Now, these sets are disjoint : if 𝑎𝑖<𝑎𝑖+1
we cannot have 𝑎𝑖+2<𝑎𝑖+1
(otherwise the condition max(𝑎𝑖,𝑎𝑖+1)>𝑎𝑖+2
is not met. So |𝐸|≤𝑚
.
To calculate the sum of the LDS of the sub-arrays, it is therefore sufficient to count for each 𝑖
such that 𝑎𝑖<𝑎𝑖+1
the number of sub-arrays 𝑎[𝑙,𝑟]
which contain 𝑖
and 𝑖+1
. It's (𝑖+1)⋅(𝑛−𝑖−1)
for 0
-indexation : a necessary and sufficient condition is that 𝑙≤𝑖
and 𝑟≥𝑖+1
.

Note that there also exists a dp approach

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int nTests; cin >> nTests;

while (nTests--) {
int nVals; cin >> nVals;
vector<int> vals(nVals);

for (int& val : vals)
cin >> val;

int sum = (nVals * (nVals + 1) * (nVals + 2))/6;
for (int i = 0; i + 1 < nVals; ++i) {
if (vals[i] < vals[i + 1]) {
sum -= (i + 1) * (nVals - i - 1);
}
}

cout << sum << endl;
}
return 0;
}