A. Замена
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Маленький Петя очень любит массивы из n целых чисел, каждое из которых лежит в диапазоне от 1 до 109, включительно. Недавно мама подарила ему один такой массив. Пете он сразу не понравился. Он решил выбрать ровно одно число из массива и заменить его на другое целое число, которое также лежит в диапазоне от 1 до 109, включительно. Нельзя менять число само на себя или же не менять ни одного числа вовсе.

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

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

Первая строка содержит одно целое число n (1 ≤ n ≤ 105) — количество чисел в массиве. Следующая строка содержит n целых чисел, разделенных одним пробелом — описание самого массива. Все элементы массива лежат в диапазоне от 1 до 109, включительно.

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

Выведите n целых чисел через пробел — минимальные возможные значения каждого из элементов массива после выполнения одной замены и сортировки.

Примеры
Входные данные
5
1 2 3 4 5
Выходные данные
1 1 2 3 4
Входные данные
5
2 3 4 5 6
Выходные данные
1 2 3 4 5
Входные данные
3
2 2 2
Выходные данные
1 2 2