# Range Sorting solution codeforces

## Range Sorting solution codeforces

The only difference between this problem and the hard version is the constraints on 𝑡 and 𝑛.

You are given an array 𝑎, consisting of 𝑛 distinct integers 𝑎1,𝑎2,,𝑎𝑛�1,�2,…,��.

Define the beauty of an array 𝑝1,𝑝2,𝑝𝑘�1,�2,…�� 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 𝑙 and 𝑟 (1𝑙<𝑟𝑘1≤�<�≤�).
• Sort the subarray 𝑝𝑙,𝑝𝑙+1,,𝑝𝑟��,��+1,…,�� in 𝑟𝑙�−� seconds.

Please calculate the sum of beauty over all subarrays of array 𝑎.

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 𝑡 (1𝑡51031≤�≤5⋅103). The description of the test cases follows.

The first line of each test case contains a single integer 𝑛 (1𝑛51031≤�≤5⋅103) — the length of the array 𝑎.

The second line of each test case consists of 𝑛 integers 𝑎1,𝑎2,,𝑎𝑛�1,�2,…,�� (1𝑎𝑖1091≤��≤109). It is guaranteed that all elements of 𝑎 are pairwise distinct.

It is guaranteed that the sum of 𝑛 over all test cases does not exceed 51035⋅103.

## Range Sorting solution codeforces

For each test case, output the sum of beauty over all subarrays of array 𝑎.

Example

input

Copy
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

Copy
1
2
8
16
232

Note

In the first test case:

• The subarray  is already sorted, so its beauty is 00.
• The subarray  is already sorted, so its beauty is 00.
• You can sort the subarray [6,4][6,4] in one operation by choosing 𝑙=1�=1 and 𝑟=2�=2. Its beauty is equal to 11.

The sum of beauty over all subarrays of the given array is equal to 0+0+1=10+0+1=1.In the second test case:

• The subarray  is already sorted, so its beauty is 00.
• The subarray  is already sorted, so its beauty is 00.
• The subarray  is already sorted, so its beauty is 00.
• The subarray [3,10][3,10] is already sorted, so its beauty is 00.
• You can sort the subarray [10,6][10,6] in one operation by choosing 𝑙=1�=1 and 𝑟=2�=2. Its beauty is equal to 21=12−1=1.
• You can sort the subarray [3,10,6][3,10,6] in one operation by choosing 𝑙=2�=2 and 𝑟=3�=3. Its beauty is equal to 32=13−2=1.

The sum of beauty over all subarrays of the given array is equal to 0+0+0+0+1+1=20+0+0+0+1+1=2.