你喜欢夏天吗?伯兰的居民就是这么做的。他们特别喜欢在炎热的夏天吃冰淇淋。所以今年夏天,柏林的居民在冰淇淋摊前排起了长队。我们知道他们每个人都随身携带一定数量的伯兰币。 Berland 的居民都是好人,所以每个人都同意以 1 美元的价格与他后面的人交换位置。更正式地说,如果a站在b的后面,那么a可以付给b 1美元,然后a和b就交换了。当然,如果a的钱为零,他就不能与b交换位置。
Berland 的居民都是奇怪的人。特别是,当他们前面排队的人的钱远远少于他们时,他们会感到不安。
你能帮助贝尔兰德的居民在队伍中形成这样的秩序,让他们都高兴吗?幸福的居民是排在队伍第一位的居民,或者是排在另一位居民前面且持有不少于美元的居民。请注意,贝尔兰德人民是有荣誉感的人民,他们同意仅以上述方式交换位置。
输入
第一行包含整数 n (1 ≤ n ≤ 200 000) — 排队的居民人数。
第二行包含 n 个空格分隔的整数 ai (0 ≤ ai ≤ 109),其中 ai 是站在该行第 i 个位置上的人的伯兰币数量。位置从行尾开始编号。
输出
如果不可能让所有居民都高兴,则打印“:(”,不带引号。否则,在单行中打印n个空格分隔的整数,其中第i个必须等于新行中位置i上的人的钱数。如果有多个答案,则打印其中任何一个。
示例
输入 #1
2 11 8
输出 #1
9 10
输入 #2
5 10 9 7 10 6
输出 #2
:(
输入 #3
3 12 3 3
输出 #3
4 4 10
注意
在第一个样本中,两个居民应该交换位置,之后第一个居民有 10 美元,他在队伍的前面,第二个居民将有 9 个硬币,他将在队伍的末尾。
在第二个示例中不可能达到预期的结果。
在第三个样本中,第一个人可以与第二个人交换,那么他们将拥有以下数量的美元:4 11 3,然后第二个人(在新行中)与第三个人交换,所得的美元数量将等于:4 4 10。在这一行中每个人都会很高兴。