MEX and Array

题意翻译

设我们有一个长度为 $k$ 的数组 $b$，并且划分为了 $c$ 段，每段为 $[l_1,r_1],[l_2,r_2],\dots,[l_c,r_c]$，满足 $l_1=1$，$r_c=k$，且 $\forall i\in[2,c]$，$r_{i-1}+1=l_i$。换句话说，数组 $b$ 中的每一个元素都在恰好一段里面。 让我们定义数组 $b$ 的如上划分的代价为 $$c+\sum\limits_{i=1}^c\operatorname{MEX}(b_{l_i},b_{l_i+1},\cdots,b_r)$$ 其中 $\operatorname{MEX}(S)$ 为最小的没有出现在集合 $S$ 中的**非负整数**。换句话说，如上划分的代价为划分的段数加上每一段的 $\operatorname{MEX}$ 值。 现在，给定一个长度为 $n$ 的数组 $a$，你需要求出其所有子段的**最大**代价的总和。我们称数组 $y$ 是数组 $x$ 的一个子段，当且仅当我们可以通过在数组 $x$ 的开头和结尾删去连续的若干个元素得到数组 $y$。 数据范围： - $t$ 组数据，$1\leqslant t\leqslant 30$。 - $1\leqslant n,\sum n\leqslant 100$。 - $0\leqslant a_i\leqslant 10^9$。 Translated by Eason_AC

题目描述

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.

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例 #1

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

输出样例 #1

4
14
26
48

说明

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