Маленький Петя очень любит массивы из n целых чисел, каждое из которых лежит в диапазоне от 1 до 109, включительно. Недавно мама подарила ему один такой массив. Пете он сразу не понравился. Он решил выбрать ровно одно число из массива и заменить его на другое целое число, которое также лежит в диапазоне от 1 до 109, включительно. Нельзя менять число само на себя или же не менять ни одного числа вовсе.
После этой замены Петя отсортировал массив по неубыванию. Теперь он хочет узнать, какое наименьшее число могло стоять на каждой позиции после замены и сортировки.
Выходные данные
Выведите n целых чисел через пробел — минимальные возможные значения каждого из элементов массива после выполнения одной замены и сортировки.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 2 3 4 5
|
1 1 2 3 4
|
|
2
|
5
2 3 4 5 6
|
1 2 3 4 5
|
|
3
|
3
2 2 2
|
1 2 2
|