Сложность: 21%
Компания Тындекс разрабатывает «Фильмопоиск» – онлайн-каталог кино, сериалов и мультфильмов.
Разумеется, в таком сервисе у каждого пользователя есть возможность оценить фильм целым числом от 1 до 10. А вот киллер-фичей «Фильмопоиска» является то, что вместо средней оценки (как на других сайтах) он отображает нижнюю медиану – оценку с номером в упорядоченном по неубыванию ряду из оценок, которые выставлены фильму на данный момент.
Напишите прототип счётчика оценок.
Входные данные
В первой строке записано число – количество оценок пользователей, которые нужно обработать. Изначально у фильма нет оценок. ()
В следующей строке записаны оценок пользователей в порядке их выставления (оценка – целое число от 1 до 10).
Выходные данные
В единственную строку выведите чисел, где -тое число – это нижняя медиана оценок от первой до -той.
Подзадачи
№ | баллы | необх. подзадачи | ограничения |
1 | 30 | - | |
2 | 30 | 1 | |
3 | 40 | 2 |
STDIN | STDOUT |
4 10 7 8 8 | 10 7 8 8 |
4 1 2 3 4 | 1 1 2 2 |