信息竞赛的真正问题

Petya非常喜欢n个整数的数列，其中数列的每个元素都是从1到10e9的整数。最近，彼佳的母亲送给他一串数字作为礼物。但是他不喜欢。他决定用一个整数代替这个数列中的一个数，这个整数也必须在1和10e9之间。不允许用数字代替自己，或者根本不代替。

替换后，petra将这个序列排列成非降序序列(即广义递增序列)。现在他想知道数列的每个位置上最小的数是多少:替换和排列后。

输入:第一行是整数n(1？≤?n？≤?10e5)，这个数表示这个数列有多少个数。第二行包含由空格分隔的n个整数——这是数据的描述部分。这个数列的每个元素都是从1到10e9的整数。

输出n个整数，用空格隔开——排列替换后数列每个位置的最小可能值。