CF549G.Happy Line

Do you like summer? Residents of Berland do. They especially love eating ice cream in the hot summer. So this summer day a large queue of n Berland residents lined up in front of the ice cream stall. We know that each of them has a certain amount of berland dollars with them. The residents of Berland are nice people, so each person agrees to swap places with the person right behind him for just 1 dollar. More formally, if person a stands just behind person b, then person a can pay person b 1 dollar, then a and b get swapped. Of course, if person a has zero dollars, he can not swap places with person b.

Residents of Berland are strange people. In particular, they get upset when there is someone with a strictly smaller sum of money in the line in front of them.

Can you help the residents of Berland form such order in the line so that they were all happy? A happy resident is the one who stands first in the line or the one in front of who another resident stands with not less number of dollars. Note that the people of Berland are people of honor and they agree to swap places only in the manner described above.

你喜欢夏天吗？贝尔兰的居民们喜欢。他们尤其喜欢在炎热的夏季吃冰淇淋。因此，在这个夏日，一队由 $n$ 名贝尔兰居民组成的长队排在了冰淇淋摊前。我们知道，每个人身上都带着一定数量的贝尔兰元（Berland dollars）。贝尔兰人非常友善，因此每个人都愿意仅用 1 美元就与自己正后方的人交换位置。更准确地说，如果人 $a$ 恰好站在人 $b$ 的正后方，那么人 $a$ 可以付给 $b$ 1 美元，之后 $a$ 和 $b$ 便互换位置。当然，如果人 $a$ 身上没有钱（即有 0 美元），他就无法与 $b$ 交换位置。

贝尔兰人是一群奇特的人。特别是，当队伍中自己前方存在某个人所持的钱数严格小于自己的钱数时，他们会感到不快。

你能否帮助贝尔兰居民们重新排成一个队列，使得所有人都开心？一个开心的居民是指：他要么排在队首，要么他前方的人所持的钱数不少于他自己所持的钱数。请注意，贝尔兰人是讲信用的人，他们只同意按上述方式交换位置。

The first line contains integer n (1 ≤ n ≤ 200 000) — the number of residents who stand in the line.

The second line contains n space-separated integers a__i (0 ≤ a__i ≤ 109), where a__i is the number of Berland dollars of a man standing on the i-th position in the line. The positions are numbered starting from the end of the line.

第一行包含一个整数 $n$（$1 \leq n \leq 200\,000$）—— 表示排成一列的居民人数。

第二行包含 $n$ 个用空格分隔的整数 $a_i$（$0 \leq a_i \leq 10^9$），其中 $a_i$ 表示站在队列中第 $i$ 个位置的人所拥有的伯兰德元数量。位置编号从队列末尾开始。

If it is impossible to make all the residents happy, print ":(" without the quotes. Otherwise, print in the single line n space-separated integers, the i-th of them must be equal to the number of money of the person on position i in the new line. If there are multiple answers, print any of them.

如果无法让所有居民都开心，则输出 :(（不带引号）。否则，在一行中输出 $n$ 个用空格分隔的整数，其中第 $i$ 个整数必须等于新队列中位置 $i$ 上的人所拥有的钱数。如果有多个答案，输出任意一个即可。

In the first sample two residents should swap places, after that the first resident has 10 dollars and he is at the head of the line and the second resident will have 9 coins and he will be at the end of the line.

In the second sample it is impossible to achieve the desired result.

In the third sample the first person can swap with the second one, then they will have the following numbers of dollars: 4 11 3, then the second person (in the new line) swaps with the third one, and the resulting numbers of dollars will equal to: 4 4 10. In this line everybody will be happy.

在第一个样例中，两名居民应交换位置；交换后，第一名居民有 10 美元，位于队列前端，第二名居民则有 9 枚硬币，位于队列末端。

在第二个样例中，无法达成所期望的结果。

在第三个样例中，第一名居民可先与第二名居民交换位置，此时他们拥有的美元数变为：4 11 3；接着，新队列中的第二名居民再与第三名居民交换位置，最终美元数变为：4 4 10。在此队列中，所有居民都将感到满意。