CF1637B.MEX and Array

Let there be an array $b_1, b_2, \ldots, b_k$. Let there be a partition of this array into segments $[l_1; r_1], [l_2; r_2], \ldots, [l_c; r_c]$, where $l_1 = 1$, $r_c = k$, and for any $2 \leq i \leq c$ holds that $r_{i-1} + 1 = l_i$. In other words, each element of the array belongs to exactly one segment.

Let's define the cost of a partition as $$c + \sum_{i = 1}^{c} \operatorname{mex}(\{b_{l_i}, b_{l_i + 1}, \ldots, b_{r_i}\}),$$ where $\operatorname{mex}$ of a set of numbers $S$ is the smallest non-negative integer that does not occur in the set $S$. In other words, the cost of a partition is the number of segments plus the sum of MEX over all segments. Let's define the value of an array $b_1, b_2, \ldots, b_k$ as the maximum possible cost over all partitions of this array.

You are given an array $a$ of size $n$. Find the sum of values of all its subsegments.

An array $x$ is a subsegment of an array $y$ if $x$ can be obtained from $y$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

给定一个数组 $b_1, b_2, \ldots, b_k$。设该数组被划分为若干段：$[l_1; r_1], [l_2; r_2], \ldots, [l_c; r_c]$，其中 $l_1 = 1$，$r_c = k$，且对任意 $2 \leq i \leq c$ 均满足 $r_{i-1} + 1 = l_i$。换言之，数组中每个元素恰好属于一段。

我们定义该划分的代价为

$$c + \sum_{i = 1}^{c} \operatorname{mex}(\{b_{l_i}, b_{l_i + 1}, \ldots, b_{r_i}\}),$$

其中集合 $S$ 的 $\operatorname{mex}$ 是不在 $S$ 中的最小非负整数。即，划分的代价等于段数加上所有段的 $\operatorname{mex}$ 值之和。我们定义数组 $b_1, b_2, \ldots, b_k$ 的值为它在所有可能划分中所能达到的最大代价。

现给定一个长度为 $n$ 的数组 $a$。请计算其所有子段的值之和。

数组 $x$ 是数组 $y$ 的一个子段，当且仅当 $x$ 可通过从 $y$ 的开头删除若干（可能为零或全部）元素、并从结尾删除若干（可能为零或全部）元素而得到。

The input contains several test cases. The first line contains one integer $t$ ($1 \leq t \leq 30$) — the number of test cases.

The first line for each test case contains one integer $n$ ($1 \leq n \leq 100$) — the length of the array.

The second line contains a sequence of integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 10^9$) — the array elements.

It is guaranteed that the sum of the values $n$ over all test cases does not exceed $100$.

输入包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 30$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 100$），表示数组的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \leq a_i \leq 10^9$），表示数组元素。

保证所有测试用例中 $n$ 的总和不超过 $100$。

For each test case print a single integer — the answer to the problem.

对于每个测试用例，输出一个整数——即该问题的答案。

In the second test case:

• The best partition for the subsegment $[2, 0, 1]$: $[2], [0, 1]$. The cost of this partition equals to $2 + \operatorname{mex}({2}) + \operatorname{mex}({0, 1}) = 2 + 0 + 2 = 4$.
• The best partition for the subsegment $[2, 0]$: $[2], [0]$. The cost of this partition equals to $2 + \operatorname{mex}({2}) + \operatorname{mex}({0}) = 2 + 0 + 1 = 3$
• The best partition for the subsegment $[2]$: $[2]$. The cost of this partition equals to $1 + \operatorname{mex}({2}) = 1 + 0 = 1$.
• The best partition for the subsegment $[0, 1]$: $[0, 1]$. The cost of this partition equals to $1 + \operatorname{mex}({0, 1}) = 1 + 2 = 3$.
• The best partition for the subsegment $[0]$: $[0]$. The cost of this partition equals to $1 + \operatorname{mex}({0}) = 1 + 1 = 2$.
• The best partition for the subsegment $[1]$: $[1]$. The cost of this partition equals to $1 + \operatorname{mex}({1}) = 1 + 0 = 1$.

The sum of values over all subsegments equals to $4 + 3 + 1 + 3 + 2 + 1 = 14$.

在第二个测试用例中：

• 子段 $[2, 0, 1]$ 的最优划分：$[2], [0, 1]$。该划分的代价为 $2 + \operatorname{mex}({2}) + \operatorname{mex}({0, 1}) = 2 + 0 + 2 = 4$。
• 子段 $[2, 0]$ 的最优划分：$[2], [0]$。该划分的代价为 $2 + \operatorname{mex}({2}) + \operatorname{mex}({0}) = 2 + 0 + 1 = 3$。
• 子段 $[2]$ 的最优划分：$[2]$。该划分的代价为 $1 + \operatorname{mex}({2}) = 1 + 0 = 1$。
• 子段 $[0, 1]$ 的最优划分：$[0, 1]$。该划分的代价为 $1 + \operatorname{mex}({0, 1}) = 1 + 2 = 3$。
• 子段 $[0]$ 的最优划分：$[0]$。该划分的代价为 $1 + \operatorname{mex}({0}) = 1 + 1 = 2$。
• 子段 $[1]$ 的最优划分：$[1]$。该划分的代价为 $1 + \operatorname{mex}({1}) = 1 + 0 = 1$。

所有子段的值之和为 $4 + 3 + 1 + 3 + 2 + 1 = 14$。