Вам дан массив из \(n\) целых неотрицательных чисел \(a_1, a_2, \dots, a_n\).
Пусть \(m\) — переменная, изначально равная \(0\). Медуза выполняет следующую операцию \(n\) раз:
- выбрать индекс \(i\) (\(1 \leq i \leq |a|\)) и удалить \(a_i\) из \(a\).
- прибавить \(\operatorname{MEX}(a)^{\dagger}\) к \(m\).
Медуза хочет узнать минимально возможное конечное значение \(m\) при оптимальном выполнении всех операций.
\(^{\dagger}\) MEX (minimum excluded) массива — это наименьшее целое неотрицательное число, которое не принадлежит массиву.
Например:
- MEX массива \([2,2,1]\) равен \(0\), так как \(0\) не принадлежит массиву.
- MEX массива \([3,1,0,1]\) равен \(2\), так как \(0\) и \(1\) принадлежат массиву, а \(2\) - нет.
- MEX массива \([0,3,1,2]\) равен \(4\), так как \(0\), \(1\), \(2\) и \(3\) принадлежат массиву, а \(4\) - нет.
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное значение \(m\) при оптимальном выполнении операций.
Примечание
В первом наборе исходных данных мы удаляем элементы из \(a\) в следующем порядке: \([5,2,\color{red}{1},0,3,0,4,0] \to [5,2,0,3,\color{red}{0},4,0] \to [5,2,\color{red}{0},3,4,0] \to [5,2,3,4,\color{red}{0}] \to [5,2,\color{red}{3},4] \to [\color{red}{5},2,4] \to [\color{red}{2},4] \to [\color{red}{4}] \to [~]\). Значение \(m\) будет равно \(1+1+1+0+0+0+0+0=3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
8
5 2 1 0 3 0 4 0
2
1 2
5
1 0 2 114514 0
8
0 1 2 0 1 2 0 3
|
3
0
2
7
|