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

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

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

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

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

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

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

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

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

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

Пример:

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

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



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