D. AghaBalaSar and Hamed
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a permutation$$$^{\text{∗}}$$$ $$$p$$$ of length $$$n$$$.

For each index $$$i$$$, you may move in one step to:

  • any index $$$j \lt i$$$, or
  • the first index $$$j \gt i$$$ such that $$$p_j \gt p_i$$$ (if such an index exists),
In other words:
  • You can always move to any position on the left.
  • On the right, you can move only to the nearest position whose value is strictly greater than the current one.
For every pair of indices $$$(i,j)$$$, let $$$f(i,j)$$$ be the minimum number of steps needed to move from $$$i$$$ to $$$j$$$. Note that if we cannot reach $$$j$$$ from $$$i$$$, then $$$f(i,j)=0$$$.

Your task is to compute:

$$$$$$\sum_{1 \le i,j \le n} f(i,j).$$$$$$

$$$^{\text{∗}}$$$A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^6$$$) — the length of $$$p$$$.

The second line of each test case contains $$$n$$$ distinct integers $$$p_1,p_2,\ldots,p_n$$$ ($$$1\le p_i\le n$$$) — the elements of $$$p$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, print a single integer — the value of $$$\sum\limits_{1 \le i,j \le n} f(i,j)$$$.

Example
Input
6
2
1 2
2
2 1
3
1 3 2
3
1 2 3
5
1 3 5 2 4
7
6 2 4 3 7 5 1
Output
2
1
4
7
15
38
Note

In the first test case, $$$f(1, 2) + f(2, 1) = 1 + 1 = 2$$$.

In the second test case, $$$f(1, 2) + f(2, 1) = 0 + 1 = 1$$$.

In the third test case, $$$f(1, 2) + f(1, 3) + f(2, 1) + f(2, 3) + f(3, 1) + f(3, 2) = 1 + 0 + 1 + 0 + 1 + 1 = 4$$$.

In the fourth test case, $$$f(1, 2) + f(1, 3) + f(2, 1) + f(2, 3) + f(3, 1) + f(3, 2) = 1 + 2 + 1 + 1 + 1 + 1 = 7$$$.