区间排序（困难版）

• 时间限制：1 秒
• 内存限制：256 MiB

题目描述

给定一个由 $n$ 个互不相同的整数组成的数组 $a$。

定义数组 $p_1,p_2,\ldots,p_k$ 的美丽值为将它排序所需的最少时间。一次操作选择 $1\le l<r\le k$，把子数组 $p_l,p_{l+1},\ldots,p_r$ 按升序排序，耗时 $r-l$ 秒。操作次数不限。

求 $a$ 的所有连续子数组的美丽值之和。

输入格式

第一行包含测试用例数 $t$。

每个测试用例的第一行包含整数 $n$，第二行包含 $n$ 个两两不同的整数 $a_1,a_2,\ldots,a_n$。

输出格式

对每个测试用例输出一行一个整数，表示答案。

样例输入 1

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

样例输出 1

1
2
8
16
232

数据范围

• $1\le t\le10^4$；
• $1\le n\le3\times10^5$；
• $1\le a_i\le10^9$，且同一测试用例内所有 $a_i$ 两两不同；
• 所有测试用例的 $n$ 之和不超过 $3\times10^5$。

题目来源：Codeforces 1827B2。