3H. Max Mex

The beauty of an array of natural numbers is defined as follows.

Choose a non-negative integer $k$ and subtract $k$ from every element of the array. If all elements remain non-negative, then this $k$ is valid. For every valid $k$, compute the MEX of the resulting array. The beauty of the array is the maximum of these MEX values over all valid $k$.

You are given a permutation of length $n$. For every pair of indices $1 \le l \le r \le n$, consider the subarray $(a_l, a_{l+1}, \dots, a_r)$ and its beauty. Output the sum of these beauties over all such pairs $(l, r)$.

Constraints:

• $1 \le t \le 10^4$
• $1 \le n \le 5 \times 10^5$
• $a_1, a_2, \ldots, a_n$ is a permutation of ${1,2,\ldots, n}$
• The sum of $n$ over all test cases does not exceed $5 \times 10^5$.