Codeforces Round 873 (Div. 1) |
---|

Finished |

binary search

dp

dsu

greedy

trees

two pointers

*2000

No tag edit access

The problem statement has recently been changed. View the changes.

×
B1. Range Sorting (Easy Version)

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

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

Example

Input

526 433 10 644 8 7 259 8 2 4 6122 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$$$.

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

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/30/2023 21:03:10 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|