该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

将数组 $p_1, p_2, \ldots p_k$ 的美定义为使用任意数量的范围排序操作对该数组进行排序所需的最短时间。在每次范围排序操作中，您将执行以下操作：

• 选择两个整数 $l$ 和 $r$ ( $1 \le l \lt r \le k$ )。
• 在 $r - l$ 秒内对子数组 $p_l, p_{l + 1}, \ldots, p_r$ 进行排序。

请计算数组 $a$ 中所有子数组的美的总和。

数组的子数组定义为数组中连续元素的序列。

输入格式

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ( $1 \le t \le 5 \cdot 10^3$ )。测试用例说明如下。

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

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\ldots, a_n$ ( $1\le a_i\le 10^9$ )。保证 $a$ 中的所有元素都是成对不同的。

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

输出格式

输出

针对每个测试用例，输出数组 $a$ 所有子数组的美的总和。

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
2
8
16
232

注

在第一个测试案例中

• 子数组 $[6]$ 已经排序，因此其美观度为 $0$ 。
• 子数组 $[4]$ 已排序，因此其美观度为 $0$ 。
• 通过选择 $l = 1$ 和 $r = 2$ 可以一次性对子数组 $[6, 4]$ 进行排序。其优美度等于 $1$ 。

给定数组的所有子数组的美度之和等于 $0 + 0 + 1 = 1$ 。