F. Sub Permutation
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a permutation$$$^{\dagger}$$$ $$$a$$$ of size $$$n$$$, with elements from $$$1$$$ to $$$n$$$.

Let's define the strength of an array $$$a$$$ of size $$$k$$$ (given all elements are distinct) as follows:-

  1. Create permutation $$$b$$$ of the same length (i.e. $$$k$$$) keeping the relative ordering of the elements in $$$b$$$ the same as of a.
  2. The last element of b (i.e. $$$b_k$$$) is the strength of array $$$a$$$.
For example, strength of array $$$[4,1,10,3]$$$ as $$$a$$$ which is equivalent to $$$[3,1,4,2]$$$ as $$$b$$$ is $$$2$$$.

Find the sum of the strength of all the non-empty subarrays of $$$a$$$.

$$$^{\dagger}$$$Permutation of size $$$k$$$ is an array which contains all integers from $$$1$$$ to $$$k$$$.

Input

Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1\leq t \leq 5\cdot 10^4$$$). The following line contains the description of each test case.

The first line contains two integers $$$n$$$ ($$$1\leq n \leq 10^6$$$) — the size of the array.

The second line contains $$$n$$$ positive integers $$$a_1$$$, $$$a_2$$$, $$$a_3$$$, $$$...$$$ ,$$$a_n$$$ ($$$1 \leq a_i \leq n$$$) — elements of the array $$$a$$$.

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

Output

Print a single integer representing the sum of the strength of all the non-empty subarrays of $$$a$$$.

Example
Input
3
1
1
3
2 1 3
4
3 4 1 2
Output
1
9
14
Note

For the second test case,

  • strength of subarray $$$[2] \equiv [1]$$$ is $$$1$$$.
  • strength of subarray $$$[1] \equiv [1]$$$ is $$$1$$$.
  • strength of subarray $$$[3] \equiv [1]$$$ is $$$1$$$.
  • strength of subarray $$$[2, 1] \equiv [2, 1]$$$ is $$$1$$$.
  • strength of subarray $$$[1, 3] \equiv [1, 2]$$$ is $$$2$$$.
  • strength of subarray $$$[2, 1, 3] \equiv [2, 1, 3]$$$ is $$$3$$$.
Total strength $$$= 1+1+1+1+2+3 = 9.$$$