Max Mex - Repovive Premier Round 2 | Repovive

3H. Max Mex

3500 pts2s256 MB

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

Input

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

Output

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

Samples

Input

Case 1

5
2 1 3 5 4

Case 2

10
4 1 7 2 10 5 3 9 6 8

Explanation

Case 1

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

Case 2

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

Output

Case 1

Case 2

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

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

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

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

3H. Max Mex

Input

Output

Samples

3H. Max Mex

Constraints:

Input

Output

Samples

Constraints: