Do you like summer? Residents of Tyago do. They especially love eating ice cream in the hot summer. So this summer day a large queue of n Tyago residents lined up in front of the ice cream stall. We know that each of them has a certain amount of Tyago dollars with them. The residents of Tyago 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 Tyago 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 Tyago 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 Tyago are people of honor and they agree to swap places only in the manner described above.

Input

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 ai (0 ≤ ai ≤ 109), where ai is the number of Tyago dollars of a man standing on the i-th position in the line. The positions are numbered starting from the end of the line.

Output

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.