小红的奶油蛋糕工坊

题号：NC312243
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小红新烤制了 $n$ 块奶油蛋糕，每块蛋糕都有一个独特的初始“甜度值”。这 $n$ 块蛋糕的甜度值恰好构成了一个长度为 $n$ 的排列 $a_1, a_2, \dots, a_n$ 。
$\hspace{15pt}$ 为了让蛋糕的口感更加和谐，小红希望调整部分蛋糕的甜度，使得工坊中至少有 $\lceil \tfrac{n}{2} \rceil$ 块蛋糕的甜度值完全相同。调整一块蛋糕的甜度是有代价的：如果将一块甜度为 $u$ 的蛋糕调整为甜度 $v$ ，所需的奶油成本为 $|u - v|$ 。
$\hspace{15pt}$ 作为一名精打细算的店长，小红希望在总成本最小的前提下，完成这个调整目标。请你帮她计算出调整后每块蛋糕的甜度值。

【名词解释】
$\hspace{15pt}$ 长度为 $n$ 的排列：由 $1,2,\dots,n$ 这 $n$ 个整数、按任意顺序组成的数组（每个整数均恰好出现一次）。例如， $\{2,3,1,5,4\}$ 是一个长度为 $5$ 的排列，而 $\{1,2,2\}$ 和 $\{1,3,4\}$ 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。
$\hspace{15pt}$ $\lceil x \rceil$ ：代表对 $x$ 进行上取整操作，得到不小于 $x$ 的最小整数。

输入描述:

第一行输入一个整数 ，表示奶油蛋糕的数量。 
第二行输入  个互不相同的整数 ，表示每块蛋糕初始的甜度值。输入保证  是一个长度为  的排列。

输出描述:

在一行上输出  个整数 ，表示在最小成本下，调整后每块蛋糕的甜度值。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

示例1

输入

复制

4
1 3 2 4

输出

复制

1 3 1 4

说明

在这个样例中，，因此至少需要有  块蛋糕的甜度值相同。其中一种可行的方案是选择初始甜度为  和  的两块蛋糕，并将它们都调整为甜度 ：
初始甜度为  的蛋糕保持不变，成本为 ；
初始甜度为  的蛋糕调整为 ，成本为 。
总成本为 。

示例2

输入

复制

5
1 3 2 5 4

输出

复制

2 2 2 5 4