310403: CF1828D1. Range Sorting (Easy Version)

D1. Range Sorting (Easy Version)time limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

The only difference between this problem and the hard 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 5 \cdot 10^3$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 5 \cdot 10^3$) — 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 $5 \cdot 10^3$.

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

题目大意：给定一个由n个不同整数组成的数组a。定义一个子数组的美观度为对其进行一系列范围排序操作所需的最短时间。每次范围排序操作包括选择两个整数l和r（1≤l
输入数据格式：第一行包含一个整数t（1≤t≤5000），表示测试用例的数量。接下来是t个测试用例的描述。每个测试用例的第一行包含一个整数n（1≤n≤5000），表示数组a的长度。第二行包含n个整数a1, a2, …, an（1≤ai≤109），保证数组a的所有元素都是两两不同的。

输出数据格式：对于每个测试用例，输出数组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题目大意：给定一个由n个不同整数组成的数组a。定义一个子数组的美观度为对其进行一系列范围排序操作所需的最短时间。每次范围排序操作包括选择两个整数l和r（1≤l