区间排序（简单版）

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

题目描述

给定一个长度为 $n$、元素两两不同的数组 $a$。

对一个数组 $p$，一次操作可以选择 $1\le l<r\le |p|$，将 $p_l,p_{l+1},\ldots,p_r$ 排序，耗时 $r-l$ 秒。定义 $p$ 的美丽值为把它变成升序数组所需的最少总时间。

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

输入格式

第一行一个整数 $t$，表示测试组数。

每组测试第一行一个整数 $n$，第二行 $n$ 个两两不同的整数 $a_i$。

输出格式

对每组测试输出一行一个整数，表示所有子数组美丽值之和。

样例输入 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\le5000$，$1\le n\le5000$，$1\le a_i\le10^9$，同一数组内元素两两不同，所有测试组的 $n$ 之和不超过 $5000$。