D. Sum of LDS
brute force; combinatorics; dp; greedy; math
You're given a permutation\(^{\text{∗}}\) \(p_1, \ldots, p_n\) such that \(\max(p_i, p_{i+1}) > p_{i+2}\) for all \(1 \leq i \leq n-2\).Compute the sum of the length of the longest decreasing subsequence\(^{\text{†}}\) of the subarray \([p_l, p_{l+1}, \ldots, p_r]\) over all pairs \(1 \leq l \leq r \leq n\).\(^{\text{∗}}\)A permutation of length \(n\) is an array consisting of \(n\) distinct integers from \(1\) to \(n\) in arbitrary order. For example, \([2,3,1,5,4]\) is a permutation, but \([1,2,2]\) is not a permutation (\(2\) appears twice in the array), and \([1,3,4]\) is also not a permutation (\(n=3\) but there is \(4\) in the array). \(^{\text{†}}\)Given an array \(b\) of size \(|b|\), a decreasing subsequence of length \(k\) is a sequence of indices \(i_1, \ldots, i_k\) such that: \(1 \leq i_1 < i_2 < \ldots < i_k \leq |b|\) \(b_{i_1} > b_{i_2} > \ldots > b_{i_k}\)
Each test contains multiple test cases. The first line contains the number of test cases \(t\) (\(1 \le t \le 10\,000\)). The description of the test cases follows. The first line of each test case contains a single integer \(n\) (\(3 \leq n \leq 500\,000\)).The second line of each test case contains \(n\) integers \(p_1, p_2, \ldots, p_n\) (\(1 \le p_i \le n\), \(p_i\) are pairwise distinct).It is guaranteed that \(\max(p_i, p_{i+1}) > p_{i+2}\) for all \(1 \leq i \leq n-2\).The sum of \(n\) over all test cases does not exceed \(500\,000\).
For each test case, output the sum over all subarrays of the length of its longest decreasing subsequence.
For any array \(a\), we define \(\text{LDS}(a)\) as the length of the longest decreasing subsequence of \(a\).In the first test case, all subarrays are decreasing. In the second one, we have \(\text{LDS}([4]) = \text{LDS}([3]) = \text{LDS}([1]) = \text{LDS}([2]) = 1\) \(\text{LDS}([4,3]) = \text{LDS}([3,1]) = 2, \text{LDS}([1, 2]) = 1\) \(\text{LDS}([4,3,1]) = 3, \text{LDS}([3,1,2]) = 2\) \(\text{LDS}([4,3,1,2]) = 3\)So the answer is \(1+1+1+1+2+2+1+3+2+3=17\).