Sum of Characteristics

You are given an array $a$ consisting of $n$ random integers from $1$ to $n$. For its subsegment $[\ell, r]$, the characteristic is the value $$C(\ell, r) = \min\limits_{\ell \le i < j \le r} \max(a_i + j, a_j + i)\text{.}$$

Your task is to calculate $$\sum\limits_{\ell = 1}^n \sum_{r = \ell + 1}^n C(\ell, r)\text{.}$$

The first line contains an integer $t$ ($1 \le t \le 3 \cdot 10^5$), the number of test cases. The test cases follow.

The first line of each test case contains an integer $n$, the size of the array ($1 \le n \le 3 \cdot 10^5$). The next line contains the array itself: $n$ integers from $1$ to $n$, picked uniformly and independently by a pseudorandom number generator.

The sum of $n$ over all test cases does not exceed $3 \cdot 10^5$.

For each test case, output a line with a single integer: the sum of characteristics over all the subsegments.