← 返回题目列表

Codeforces · 135/A

A. 更换

中文机器翻译题面 查看原题

小Petya非常喜欢由n个整数组成的数组,其中每个整数的范围都在1到109(含)之间。最近他收到了一套这样的阵列作为他母亲送给他的礼物。彼佳立刻不喜欢这样。他决定从数组中精确选择一个元素,并将其替换为另一个也在 1 到 109 范围内(含 1 和 109)的整数。不允许用其自身替换号码或根本不更改任何号码。

替换后,Petya 按数字非递减对数组进行排序。现在他想知道每个位置:在替换和排序后最少可以占据多少个位置。

输入

第一行包含一个整数 n (1 ≤ n ≤ 105),它表示数组有多少个数字。下一行包含 n 个空格分隔的整数——数组的描述。数组的所有元素都在 1 到 109 的范围内(包含 1 和 109)。

输出

打印 n 个空格分隔的整数 — 执行一次替换和排序后每个数组元素的最小可能值。

示例

输入 #1

5
1 2 3 4 5

输出 #1

1 1 2 3 4

输入 #2

5
2 3 4 5 6

输出 #2

1 2 3 4 5

输入 #3

3
2 2 2

输出 #3

1 2 2