Разработчик: Даниил Орешников
Самое примитивное решение задачи заключается в эмуляции процесса, описанного в условии. К сожалению, количество действий, необходимое, чтобы завершить процесс, может быть слишком большим, поэтому требуется эту эмуляцию оптимизировать.
Для полного решения достаточно одного наблюдения: с каждым следующим шагом в последовательности становится все больше и больше одинаковых чисел. Пусть у нас x минимальных чисел и y максимальных, тогда
Таким образом, давайте поддерживать дек (deque) упорядоченных по величине чисел и количеств их вхождений в последовательность. За одно действие будем вынимать из дека минимальное и максимальное число, после чего массово обрабатывать 2min(x, y) ходов.
Останется только аккуратно отследить момент, когда различных чисел становится не больше двух. Время работы такого решения пропорционально n.