B2. Range Sorting (Hard Version)
binary search; data structures; dp; greedy
The only difference between this problem and the easy version is the constraints on \(t\) and \(n\).You are given an array \(a\), consisting of \(n\) distinct integers \(a_1, a_2, \ldots, a_n\). Define the beauty of an array \(p_1, p_2, \ldots p_k\) as the minimum amount of time needed to sort this array using an arbitrary number of range-sort operations. In each range-sort operation, you will do the following: Choose two integers \(l\) and \(r\) (\(1 \le l < r \le k\)). Sort the subarray \(p_l, p_{l + 1}, \ldots, p_r\) in \(r - l\) seconds. Please calculate the sum of beauty over all subarrays of array \(a\).A subarray of an array is defined as a sequence of consecutive elements of the array.
Each test contains multiple test cases. The first line contains the number of test cases \(t\) (\(1 \le t \le 10^4\)). The description of the test cases follows.The first line of each test case contains a single integer \(n\) (\(1 \le n \le 3 \cdot 10^5\)) — the length of the array \(a\).The second line of each test case consists of \(n\) integers \(a_1,a_2,\ldots, a_n\) (\(1\le a_i\le 10^9\)). It is guaranteed that all elements of \(a\) are pairwise distinct.It is guaranteed that the sum of \(n\) over all test cases does not exceed \(3 \cdot 10^5\).
For each test case, output the sum of beauty over all subarrays of array \(a\).
In the first test case: The subarray \([6]\) is already sorted, so its beauty is \(0\). The subarray \([4]\) is already sorted, so its beauty is \(0\). You can sort the subarray \([6, 4]\) in one operation by choosing \(l = 1\) and \(r = 2\). Its beauty is equal to \(1\). The sum of beauty over all subarrays of the given array is equal to \(0 + 0 + 1 = 1\).In the second test case: The subarray \([3]\) is already sorted, so its beauty is \(0\). The subarray \([10]\) is already sorted, so its beauty is \(0\). The subarray \([6]\) is already sorted, so its beauty is \(0\). The subarray \([3, 10]\) is already sorted, so its beauty is \(0\). You can sort the subarray \([10, 6]\) in one operation by choosing \(l = 1\) and \(r = 2\). Its beauty is equal to \(2 - 1 = 1\). You can sort the subarray \([3, 10, 6]\) in one operation by choosing \(l = 2\) and \(r = 3\). Its beauty is equal to \(3 - 2 = 1\). The sum of beauty over all subarrays of the given array is equal to \(0 + 0 + 0 + 0 + 1 + 1 = 2\).