题目描述

给定一个数组 $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}\})$，其中 $\operatorname{mex}$ 表示集合 $S$ 中未出现的最小非负整数。也就是说，划分的代价等于段数加上所有段的 MEX 之和。我们定义数组 $b_1, b_2, \ldots, b_k$ 的价值为所有划分方式中代价的最大值。

现在给定一个长度为 $n$ 的数组 $a$。请你计算其所有子段的价值之和。数组 $x$ 是数组 $y$ 的子段，当且仅当 $x$ 可以通过从 $y$ 的开头和结尾各删除若干（可能为零或全部）元素得到。

输入格式

输入包含若干组测试数据。第一行包含一个整数 $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$。

输出格式

对于每组测试数据，输出一个整数，表示该组数据的答案。

说明/提示

在第二组测试数据中：

• 子段 $[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$。

由 ChatGPT 4.1 翻译

样例

4
2
1 2
3
2 0 1
4
2 0 5 1
5
0 1 1 0 1

4
14
26
48