在森林幽靜的一隅，有一村落居住著 n 只兔子。

    某個月光皎潔的夜晚，這些兔子列成一隊，準備開始一場集結(jié)跳躍活動。村落中的每只兔子都占據(jù)一個位置，對于第 i 只兔子，其位置為 pi 。我們稱位置較小的為左邊，位置較大的為右邊。

    按照兔子村落的習(xí)俗，每只兔子都會選擇距離自己最近的兔子作為同伴，并向同伴所在的方向進行跳躍。如果一只兔子左邊和右邊的兔子距離它一樣近，那么它會選擇左邊的兔子作為同伴。

    兔子的每次跳躍，只能向左或向右移動一個單位距離。也就是說，如果一只兔子當(dāng)前位于 x 的位置，那么它下一次跳躍后會到達 x ? 1 或者 x + 1 的位置。

當(dāng)兩只相互靠近的兔子之間的距離為 1 時，左邊的兔子會停在原地，而右邊的兔子會跳到左邊兔子的位置上，完成集結(jié)。

    兔子們會一直跳躍，直到與自己最初選擇的同伴完成集結(jié)后停下。

    請問，當(dāng)所有兔子都完成集結(jié)后，每只兔子都分別位于哪個位置上？

輸入的第一行包含一個整數(shù) n，表示兔子的數(shù)量。

第二行包含 n 個整數(shù) p1, p2, · · · , pn ，相鄰整數(shù)之間使用一個空格分隔，表示每只兔子的初始位置。

輸出一行包含 n 個整數(shù)，表示每只兔子完成集結(jié)后的位置。

5
2 5 7 9 1

1 6 6 6 1

【樣例說明】   

 兔子 1 選擇的同伴為兔子 5，兔子 5 選擇的同伴為兔子 1。由于它們彼此間的距離為 1，因此兔子 5 會停在原地，而兔子 1 會跳到位置 1 上，與兔子 5完成集結(jié)。

    兔子 2 選擇的同伴為兔子 3，兔子 4 選擇的同伴也為兔子 3。對于兔子 3來說，兔子 2 和兔子 4 與它的距離相同，所以它會選擇左邊的兔子 2 作為同伴。兔子 2 會向右跳一個位置，兔子 3 會向左跳一個位置，兔子 4 會向左跳一個位置。此時，兔子 2 和兔子 3 均位于位置 6，完成集結(jié)（停止跳躍）。兔子 4會繼續(xù)向左跳躍，直到跳到位置 6 后與兔子 3 完成集結(jié)。

【評測用例規(guī)模與約定】

    對于 40% 的評測用例，2 ≤ n ≤ 500，1 ≤ pi ≤ 105，p1, p2, · · · , pn 各不相同。

    對于所有評測用例，2 ≤ n ≤ 105，1 ≤ pi ≤ 109，p1, p2, · · · , pn 各不相同。