ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

2080. Карточки

Ограничение времени: 2.0 секунды
Ограничение памяти: 256 МБ
Женя давно уже не бедный студент, живёт в большом городе и работает в престижной компании. Теперь в его кошельке не папина кредитка с нулевым балансом, а целая стопка собственных карточек: зарплатная банковская карта, карточка для оплаты обедов, проездной в метро, скидочные карточки кафе и магазинов.
Каждая неделя у Жени проходит по устоявшемуся распорядку: он передвигается одним и тем маршрутом, посещает одни и те же места. Спустя месяцы жизни в большом чужом городе он, наконец, может ни о чем не думать, а без проблем следовать понятному набору действий!
Впрочем, одна проблема у Жени всё-таки есть. Иногда в магазине, в кафе или даже на входе в метро он вынужден долго искать в кошельке нужную карточку. Это отнимает его драгоценное время и сбивает жизнь с привычного ритма.
Карточки в Женином кошельке хранятся одной стопкой. Женя хочет, чтобы каждый раз, когда у него возникает необходимость воспользоваться картой, наверху стопки оказывалась именно та, которая ему нужна. При этом для Жени не проблема после использования карты убрать её в определённое место стопки.
Зная, в каком порядке будут использоваться карты, несложно складывать их так, чтобы сверху всегда оказывалась нужная. Женя мог бы решить эту задачу, но ему не хочется. Так что займитесь-ка этим сами.

Исходные данные

В первой строке записано два числа — n и k (1 ≤ n, k ≤ 105) — общее количество карточек у Жени в кошельке и количество раз, которое Женя использует свои карточки в течение недели. Карточки пронумерованы целыми числами от 1 до n.
Во второй строке через пробел записано k чисел a1, a2, …, ak (1 ≤ ain) — номера карточек, перечисленные в порядке их использования.

Результат

Выведите k+1 строку.
В первой строке должны находиться записанные через пробел n чисел от 1 до n — порядок, в котором карты требуется расположить изначально, от самой верхней до самой нижней.
В (i + 1)-й строке должно содержаться одно число — сколько карточек будет располагаться над ai-й сразу после её возвращения в кошелёк.
Если существует несколько возможных решений, выведите любое.

Пример

исходные данныерезультат
3 5
3 1 2 2 1
3 1 2 
2
1
0
1
0
Автор задачи: Евгений Курпилянский, подготовка — Михаил Вяцков