CF2128D Sum of LDS

给定一个排列 $ ^{\text{∗}} $ $ p_1, \ldots, p_n $，满足对于所有 $ 1 \leq i \leq n-2 $ 都有 $ \max(p_i, p_{i+1}) > p_{i+2} $。 计算所有子数组 $ [p_l, p_{l+1}, \ldots, p_r] $（其中 $ 1 \leq l \leq r \leq n $）的最长递减子序列 $ ^{\text{†}} $ 长度的总和。 $ ^{\text{∗}} $ 长度为 $ n $ 的排列是指由 $ 1 $ 到 $ n $ 的 $ n $ 个不同整数按任意顺序组成的数组。例如，$ [2,3,1,5,4] $ 是一个排列，但 $ [1,2,2] $ 不是排列（因为 $ 2 $ 出现了两次），$ [1,3,4] $ 也不是排列（当 $ n=3 $ 时出现了 $ 4 $）。 $ ^{\text{†}} $ 给定一个大小为 $ |b| $ 的数组 $ b $，长度为 $ k $ 的递减子序列是指满足以下条件的下标序列 $ i_1, \ldots, i_k $： - $ 1 \leq i_1 < i_2 < \ldots < i_k \leq |b| $ - $ b_{i_1} > b_{i_2} > \ldots > b_{i_k} $

每个测试包含多个测试用例。第一行包含测试用例的数量 $ t $（$ 1 \le t \le 10\,000 $）。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $ n $（$ 3 \leq n \leq 500\,000 $）。 每个测试用例的第二行包含 $ n $ 个整数 $ p_1, p_2, \ldots, p_n $（$ 1 \le p_i \le n $，且所有 $ p_i $ 互不相同）。 保证对于所有 $ 1 \leq i \leq n-2 $ 都有 $ \max(p_i, p_{i+1}) > p_{i+2} $。 所有测试用例的 $ n $ 之和不超过 $ 500\,000 $。

对于每个测试用例，输出所有子数组的最长递减子序列长度的总和。

对于任意数组 $ a $，我们定义 $ \text{LDS}(a) $ 为 $ a $ 的最长递减子序列的长度。 在第一个测试用例中，所有子数组都是递减的。 在第二个测试用例中： $ \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 $ 因此答案为 $ 1+1+1+1+2+2+1+3+2+3=17 $。