CF1827B2.Range Sorting (Hard Version)

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 \lt 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.

此题与简单版本的唯一区别在于 $t$ 和 $n$ 的约束条件。

给你一个由 $n$ 个互不相同的整数 $a_1, a_2, \ldots, a_n$ 构成的数组 $a$。

定义数组 $p_1, p_2, \ldots, p_k$ 的美观度（beauty）为：使用任意次数的区间排序操作将其排序所需的最短时间。每次区间排序操作执行如下步骤：

• 选择两个整数 $l$ 和 $r$（满足 $1 \le l \lt r \le k$）；
• 将子数组 $p_l, p_{l + 1}, \ldots, p_r$ 进行排序，耗时 $r - l$ 秒。

请计算数组 $a$ 的所有子数组的美观度之和。

数组的一个子数组定义为该数组中连续的一段元素所构成的序列。

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 3 \cdot 10^5$）—— 数组 $a$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\ldots, a_n$（$1\le a_i\le 10^9$）。保证数组 $a$ 中所有元素两两不同。

保证所有测试用例的 $n$ 值之和不超过 $3 \cdot 10^5$。

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

对于每个测试用例，输出数组 $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$.

在第一个测试用例中：

• 子数组 $[6]$ 已经有序，因此其优美值为 $0$。
• 子数组 $[4]$ 已经有序，因此其优美值为 $0$。
• 你可以通过选择 $l = 1$ 和 $r = 2$ 对子数组 $[6, 4]$ 执行一次操作将其排序。其优美值等于 $1$。

给定数组所有子数组的优美值之和为 $0 + 0 + 1 = 1$。

在第二个测试用例中：

• 子数组 $[3]$ 已经有序，因此其优美值为 $0$。
• 子数组 $[10]$ 已经有序，因此其优美值为 $0$。
• 子数组 $[6]$ 已经有序，因此其优美值为 $0$。
• 子数组 $[3, 10]$ 已经有序，因此其优美值为 $0$。
• 你可以通过选择 $l = 1$ 和 $r = 2$ 对子数组 $[10, 6]$ 执行一次操作将其排序。其优美值等于 $2 - 1 = 1$。
• 你可以通过选择 $l = 2$ 和 $r = 3$ 对子数组 $[3, 10, 6]$ 执行一次操作将其排序。其优美值等于 $3 - 2 = 1$。

给定数组所有子数组的优美值之和为 $0 + 0 + 0 + 0 + 1 + 1 = 2$。