Max Mex - Repovive Premier Round 2 | Repovive

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/7/problems/H

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/7/problems/H

Repovive

Max Mex - Repovive Premier Round 2 | Repovive | Repovive

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$ .

t \\[0.5em] \left. \begin{array}{l} n \\[0.2em] a_1 \quad a_2 \quad \dots \quad a_n \end{array} \right\} \times t

\left. \begin{array}{l} \text{ans} \end{array} \right\} \times t

consider the subarray $[1..3]$ which is $[2,1,3]$ . Its minimum is $1$ . If we choose $k=1$ and subtract it from all elements, we get $[1,0,2]$ (all non-negative). The MEX of $[1,0,2]$ is $3$ , so the beauty of this subarray is at least $3$ (and it is exactly $3$ ).

There are $55$ subarrays and the answer is $100$ .

7H. Max Mex

Constraints:

Input

Output

Samples

Constraints: