Задача №1733. Золотая середина
Центральным элементом набора из \(k\) чисел называется такой элемент, который после сортировки набора будет занимать в нём центральную позицию (то есть позицию номер ⌈k / 2⌉, считая с единицы).
Числа добавляются в изначально пустой набор в заданном порядке. Требуется определить значения центрального элемента после добавления каждого числа.
Входные данные
Входной файла содержит количество чисел n, за которым следуют n целых чисел ai в порядке их добавления в набор. 1 ≤ n ≤ \(10^6\), \(−10^9 \le a_i \le 10^9\).
Выходные данные
Выходной файл должен содержать n целых чисел — значения центрального элемента после каждого добавления.
Примеры тестов
Входные данные
3 5 3 4
Выходные данные
5 3 4
Входные данные
5 1 2 3 2 4
Выходные данные
1 1 2 2 2
Сдать: для сдачи задач необходимо войти в систему