D. Greedy Counting
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Shimoe Koharu is given an array $$$a$$$ and required to find the length of its longest increasing sequence. Since Koharu doesn't know the classical problem nor the dynamic programming approach, she picks the sequence by greedy:

  1. Let $$$i:=1$$$ be the current index and the answer be $$$1$$$.
  2. For $$$j \gt i$$$, pick the smallest $$$j$$$ such that $$$a_j \gt a_i$$$. If she cannot find such $$$j$$$, end the procedure.
  3. Let $$$i:=j$$$ and increase the answer by $$$1$$$. Then jump to Step $$$2$$$.

This algorithm is clearly wrong: for example, if $$$a=[1,4,2,3]$$$, she will get $$$[1,4]$$$ instead of the correct $$$[1,2,3]$$$. As the consultant of the Supplemental Lessons Club, you're a bit annoyed and assign her to find such sequences on all subarrays of $$$a$$$ via her approach, before she needs to sum up the length of these sequences.

However, you need to judge if her result is right. So it's now your task to calculate the sum.

Input

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

The first line of each test case contains one integer $$$n$$$ ($$$1\le n\le 4\cdot 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ ($$$1\le a_i\le n$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$4\cdot 10^5$$$.

Output

For each test case, output one integer — the sum of the length of all sequences obtained by Koharu's approach on all subarrays of $$$a$$$.

Example
Input
3
1
1
4
1 4 2 3
6
1 1 4 5 1 4
Output
1
14
39