This is the hard version of the problem. The difference between the versions is that in this version, you must compute the sum of values over all subsegments. You can hack only if you solved all versions of this problem.

Let's define an algorithm to generate a sequence of $$$m+k$$$ integers as follows:

First, receive a sequence $$$x$$$ of $$$m$$$ integers as input. If $$$k=0$$$, terminate immediately and return the sequence $$$x$$$.
Then, select any index $$$1 \le i \le |x|$$$ and insert $$$(x_i+1)$$$ immediately after the element $$$x_i$$$.
If $$$x$$$ contains exactly $$$m+k$$$ integers, terminate and return the sequence $$$x$$$. Otherwise, return to the second step.

Alice knows that this algorithm was used by an ancient civilization in order to hide their secrets safely. Alice wants to learn the knowledge that they wanted to hide, but it is not an easy job to infer the input from the output of the algorithm.

For a sequence $$$b$$$ of $$$n$$$ integers, let us define $$$f(b)$$$ as the length of the shortest sequence that could be given as an input for the algorithm to generate $$$b$$$.

Given a sequence $$$a$$$ of $$$n$$$ integers, please compute the value of the following sum

$$$$$$\sum_{l=1}^n {\sum_{r=l}^n {f([a_l,a_{l+1},\ldots,a_r])}}$$$$$$

In other words, you must find the sum of $$$f(c)$$$ over all subsegments$$$^{\text{∗}}$$$ $$$c$$$ of $$$a$$$.

$$$^{\text{∗}}$$$A sequence $$$a$$$ is a subsegment of a sequence $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. Two subsegments are considered different if the sets of positions of the deleted elements are different.

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 \le n \le 300\,000$$$).

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

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$300\,000$$$.

Output

For each test case, output the answer on a separate line.

Note

In the first test case, all subsegments of $$$a=[1,2,3,4,5]$$$ can be generated from a sequence of length $$$1$$$.

In the second test case, all subsegments of $$$a=[1,3,5,7,9]$$$ cannot be generated from any shorter sequence than itself.

Lost Civilization (Hard Version)

Examples