Sum of Longest Increasing Subarray Lengths

Given an array of N integers, for each element you need to calculate the length of the longest strictly increasing contiguous subarray that ends at that element. Formally, define f(i) as follows:

\( f(1)=1, \quad f(i)=\begin{cases} f(i-1)+1, & \text{if } a_i > a_{i-1} \\ 1, & \text{otherwise} \end{cases} \)

Your task is to compute the sum \( \sum_{i=1}^{N} f(i) \) for the given array. The input consists of multiple test cases. For each test case, output the corresponding sum on a separate line.

Example:

• For the array [1, 2, 2, 3, 4], the longest increasing subarray lengths ending at each index are [1, 2, 1, 2, 3] and their sum is 9.
• For the array [3, 2, 1], the output is 3 as each element starts a new subarray.

inputFormat

The input is read from the standard input (stdin) and is formatted as follows:

T
N1
a_{1,1} a_{1,2} ... a_{1,N1}
N2
a_{2,1} a_{2,2} ... a_{2,N2}
...
NT
a_{T,1} a_{T,2} ... a_{T,NT}

Where:

• T is the number of test cases.
• For each test case, the first integer is N, the size of the array, followed by N space-separated integers.

outputFormat

For each test case, output the sum of the lengths of the longest strictly increasing subarrays ending at each element. Each result should be printed on a new line to the standard output (stdout).

## sample

1
5
1 2 2 3 4

9

</p>