Разбор добавил Александр Чистяков

Создадим массив длины MAX_HEIGHT = (10^5+10), где в i-той ячейке будет стоять 1, если на данный
момент в строю присутствует солдат данного роста, и 0 - если отсутствует.
На данном массиве будем поддерживать RSQ, умеющее за log(MAX_HEIGHT) действий отвечать на запрос:
сколько человек в строю имеет рост [i; MAX_HEIGHT). Наиболее простой в реализации структурой,
обрабатывающей подобные запросы является дерево Фенвика.

Теперь, чтобы добавить в строй солдата ростом h достаточно вывести сумму элементов на интервале
(h, MAX_HEIGHT) - так мы узнаем его номер в строю. И поставив 1 в ячейку с индексом h выполнить
update(h, +1) в RSQ.

Удаление солдата из строя тоже не особо трудоёмкое задание. Чтобы удалить солдата, стоящего i-тым в
строю, достаточно бинарным поиском на отрезке [0; MAX_HEIGHT) найти такое минимальное h, что
сумма элементов на интервале (h; MAX_HEIGHT) равна i. После чего выполнить update(h, -1).

Суммарная сложность такого алгоритма составляет:
a * log(MAX_HEIGHT) + b * log^2(MAX_HEIGHT), где a - количество запросов типа 1, b - количество
запросов типа 2