CF549G Happy Line

你喜欢夏天吗？Berland 的居民很喜欢。他们尤其喜欢在炎热的夏天吃冰激凌。就在这个夏日，有 $n$ 个 Berland 的居民在冰激凌摊前排起了长队。我们知道，每个人手上有一定数量的 Berland 元。 Berland 的居民都是好人，所以每个人都同意只花 1 元与他身后的那个人交换位置。更正式地说，如果 $a$ 站在 $b$ 的正后方，那么 $a$ 可以支付 $b$ 1 元，然后 $a$ 和 $b$ 可以交换位置。当然，如果 $a$ 没有钱了，就不能与 $b$ 交换。 Berland 的居民有些奇怪，特别是在队伍中站在比自己钱少的人前面会让他们感到不快。 请你帮助 Berland 的居民们把队伍调整成让所有人都满意的顺序。一个满意的居民是指：他要么站在队伍的最前头，要么他身前的那个人拥有的钱数不少于他。注意，Berland 的居民都是守信用的人，他们只允许按照上述方式交换位置。

第一行包含一个整数 $n$（$1 \leq n \leq 200000$），表示排队的居民人数。 第二行包含 $n$ 个用空格分隔的整数 $a_i$（$0 \leq a_i \leq 10^{9}$），其中 $a_i$ 表示站在第 $i$ 个位置（从队伍尾开始编号）的人的 Berland 元数量。

如果无法让所有居民满意，输出 ":("（不含引号）。否则，在一行输出 $n$ 个空格分隔的整数，第 $i$ 个为新队列中第 $i$ 位的人的钱数。如果有多组答案，输出任意一种都可以。

在第一个样例中，两人需要交换位置，此后第一个人有 10 元且在队首，第二个人有 9 元且在队尾。 在第二个样例中，无法达到所有人满意的状态。 在第三个样例中，第一个人可以和第二个人交换位置，然后他们的钱数变为 $4\ 11\ 3$，之后新的第二个人和第三个人交换，最终队伍变为 $4\ 4\ 10$，此时所有人都满意。 由 ChatGPT 5 翻译