310395: CF1827B2. Range Sorting (Hard Version)

B2. Range Sorting (Hard Version)time limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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$.

Output

For each test case, output the sum of beauty over all subarrays of array $a$.

ExampleInput

5
2
6 4
3
3 10 6
4
4 8 7 2
5
9 8 2 4 6
12
2 6 13 3 15 5 10 8 16 9 11 18

Output

1
2
8
16
232

Note

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$.

题意翻译

对一个数组 $\{p_i\}$ 的一段区间 $[l,r]$ 排序的代价为 $r-l$ ，对整个数组 $p_i$ 排序的代价为选定若干区间并排序，使得整个数组有序的代价之和。 求 $\{a_i\}$ 的所有子段排序的代价之和。