Ali has an array of $n$ distinct numbers.
He wants to calculate the sum of F(L, R), where F(L, R) is the mex of the numbers in the subarray [L, R] (0 <= L <= R <= n-1).
Knowing that the mex of an array is the minimum excluded number (mex(1,2) = 0, mex(0,1,2)= 3).
Can you help Ali to find the sum of F(L, R) for all subarrays?
The input consists of multiple test cases. The first line contains a single integer $t (1 \le t \le 10^4)$ --- the number of test cases.
The first line of each test case contains one integer $n (1 \le n \le 2 \cdot 10^5)$---the number of elements in the array $a$.
The second line of each test case contains $n$ integers $a_1,a_2, \dots ,a_n (0 \le a_i \le n-1)$ the elements of the array $a$.
It's guaranteed that each value in the array $a$ appears exactly once and the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
The sum of F(L, R) for all subarrays.
| Input | Output |
|---|---|
2 5 0 1 2 3 4 5 4 0 1 3 2 Copy
|
15 19 Copy
|
The answer is:
number of subarrays containing 1
+ number of subarrays containing 1 and 2
+ number of subarrays containing 1 and 2 and 3
+ ....
Iterate over the values of the elements from 1 to N and maintain the min and max index.