Компания Тындекс разрабатывает «Фильмопоиск» – онлайн-каталог кино, сериалов и мультфильмов.

Разумеется, в таком сервисе у каждого пользователя есть возможность оценить фильм целым числом от 1 до 10. А вот киллер-фичей «Фильмопоиска» является то, что вместо средней оценки (как на других сайтах) он отображает нижнюю медиану – оценку с номером $\lceil \frac{n}{2} \rceil$ в упорядоченном по неубыванию ряду из $n$ оценок, которые выставлены фильму на данный момент.

Напишите прототип счётчика оценок.

Входные данные

В первой строке записано число $q$ – количество оценок пользователей, которые нужно обработать. Изначально у фильма нет оценок. ($1 \le q \le 10^5$)

В следующей строке записаны $q$ оценок пользователей в порядке их выставления (оценка – целое число от 1 до 10).

Выходные данные

В единственную строку выведите $q$ чисел, где $i$-тое число – это нижняя медиана оценок от первой до $i$-той.

Подзадачи