write a go solution for Description:
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,ldotsp_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<=l<r<=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 Format:
Each test contains multiple test cases. The first line contains the number of test cases t (1<=t<=5*10^3). The description of the test cases follows.

The first line of each test case contains a single integer n (1<=n<=5*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<=a_i<=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*10^3.

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

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.

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.. Output only the code with no comments, explanation, or additional text.