设一个数组 $$$b_1, b_2, \ldots, b_k$$$。将该数组划分为段 $$$[l_1; r_1],[l_2; r_2],\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$$$ 是集合 $$$S$$$ 中不出现的最小非负整数。换句话说,分区的成本是段的数量加上所有段的 MEX 之和。让我们将数组 $$$b_1, b_2, \ldots, b_k$$$ 的值定义为该数组所有分区的最大可能成本。
给定一个数组 $$$a$$$,大小为 $$$n$$$。求其所有子段的值之和。
数组 $$$x$$$ 是数组 $$$y$$$ 的子段,如果 $$$x$$$ 可以通过删除开头的几个(可能是零个或全部)元素和末尾的几个(可能是零个或全部)元素从 $$$y$$$ 获得。
输入
输入包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 30$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 100$$$) — 数组的长度。
第二行包含整数序列 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$) — 数组元素。
保证所有测试用例的$$$n$$$ 值之和不超过$$$100$$$。
输出
对于每个测试用例,打印一个整数 - 问题的答案。
示例
输入 #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
注意
在第二个测试用例中:
- 子段 $$$[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$$$。