Пусть есть массив \(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\) удалением нескольких (возможно, ни одного или всех) элементов из начала и нескольких (возможно, ни одного или всех) элементов из конца.
Примечание
Рассмотрим второй набор входных данных:
- Лучшее разбиение подотрезка \([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\).