Автор задачи и разработчик: Егор Юлин
Отметим некоторые факты, после чего предложим алгоритм построения массива, в котором будет максимальный ответ.
Если в массиве встречается число $$$a_i$$$, при этом оно уже было раньше, то ничего не изменится. Из-за этого все повторения чисел можно расположить в конце в любом порядке.
Обозначим $$$b_i = \mathtt{mex}(a_1, \ldots, a_i)$$$. Заметим, что массив $$$b$$$ не убывает. Кроме того, все повторения чисел мы переместили в конец, тогда рассмотрим массив $$$a$$$, в котором все числа различны. Чтобы получить максимальный $$$\mathrm{mex}(b)$$$, мы хотим получить массив $$$b$$$ вида $$$(0, 1, 2, 3, \ldots)$$$.
Докажем, что если отсортировать массив $$$a$$$, после чего расположить его элементы как $$$(a_n, a_1, a_2, a_3, \ldots)$$$, то массив $$$b$$$ получится оптимальным.
Действительно,
Тогда можно отсортировать $$$a$$$, все неуникальные числа перенести в конец, f на первую позицию поставить максимум. После этого останется посчитать $$$\mathrm{mex}$$$ на префиксах (это сделается с помощью std::map), после этого посчитать итоговый $$$\mathrm{mex}$$$. Время работы: $$$\mathcal{O}(n \log{n})$$$.