0366. Перестановка

Имя входного файла: permutation.in
Имя выходного файла: permutation.out
Ограничение по времени: 2 s
Ограничение по памяти: 256 megabytes

Егор – самый счастливый мальчик на свете, ведь у него есть своя собственная перестановка!

Перестановка из N чисел – это набор целых чисел от 1 до n, в котором каждое число встречается ровно один раз. Например, \{1,4,3,2\} – перестановка из четырех чисел, а \{1,1,3,4\} и \{1,5,2,3\} – нет.

Необычный мальчик Антоша очень завидует Егору. Еще бы, у Антоши нет своей перестановки, а только набор из N целых чисел ai. Когда Егор в очередной раз хвастался перестановкой, Антоша твердо решил заполучить свою собственную перестановку из N чисел из имеющегося набора.

Антоша может совершить мысленное усилие и заменить число в своём наборе на любое другое число. Однако для совершения такого усилия ему требуется съесть шоколадку, поэтому он хочет совершить минимальное количество усилий и получить в результате из своего набора перестановку.

Заметьте, что порядок чисел важен и Антоша не может менять числа местами, а может только одно число заменить на другое.

Формат входного файла

В первой строке входного файла находится целое число N – количество чисел в наборе (1 ≤ N ≤ 299 299). Во второй строке входного файла находятся N разделенных пробелами целых чисел ai из набора Антоши (1 ≤ ai ≤ 109).

Формат выходного файла

В единственной строке выходного файла выведите N целых чисел – перестановку, полученную описанным способом за минимальное количество обращений. Если ответов несколько, выведите любой.

Пример:

permutation.inpermutation.out
3 1 4 3 1 2 3
3 1 2 3 1 2 3
3 1 1 3 1 2 3


Источник: Открытый зимний чемпионат ПетрГУ по программированию, 15 декабря 2013

Обсудить       Отправить решение



Версия для печати