Сумма НУП

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;
}