小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