B'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: 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 <= t <= 10^4 ). The description of the test cases follows. The first line of each test case contains a single integer n ( 1 <= n <= 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 <= a_i <= 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: In the second test case: '...