Автор задачи и разработчик: Даниил Голов Будем рассматривать описанный в задаче процесс с конца. Представим, что все числа уже добавлены в множество. Тогда медиана этого набора вычисляется однозначно — это просто медиана всех чисел из $$$a$$$. Если эта медиана нецелая, что возможно только при четной длине $$$a$$$, то ответ $$$-1$$$, так как вне зависимости от порядка добавления нецелая медиана будет достигнута.
Теперь будем удалять числа из нашего множества так, чтобы медиана оставалась целой. Этот процесс будет аналогичен добавлению, только протечет в обратном порядке, соответственно, в конце ответ нужно будет развернуть.
Если множество четного размера и имеет целую медиану, то мы можем удалить сначала минимум, потом максимум, и медиана все еще останется той же, либо множество опустеет. То есть мы сократим размер множества на 2, оставив медиану целой на любом шаге.
Если же множество нечетного размера и содержит более одного элемента, то посмотрим на три центральных элемента в отсортированном порядке. Какие-то два из них точно дадут четную сумму по принципу Дирихле. Тогда удалим третий элемент и получим множество четного размера с целой медианой, которое мы строить уже умеем.