B. MEX и массив
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Пусть есть массив $$$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$$$ — это минимальное неотрицательное целое число, которое не встречается в множестве $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите единственное целое число — ответ на задачу.

Пример
Входные данные
4
2
1 2
3
2 0 1
4
2 0 5 1
5
0 1 1 0 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$$$.