← 返回题目列表

Codeforces · 1028/E

E. 恢复阵列

中文机器翻译题面 查看原题

在讨论 Codeforces 回合的正确问题 A 时,Kostya 创建了一个正整数循环数组 $$$a_1, a_2, \ldots, a_n$$$。由于演讲很长而且前景不佳,Kostya 创建了一个新的循环数组 $$$b_1, b_2, \ldots, b_{n}$$$ ,以便 $$$b_i = (a_i \mod a_{i + 1})$$$,其中我们采用 $$$a_{n+1} = a_1$$$。这里 $$$mod$$$ 是模运算。当谈话变得有趣时,Kostya 完全忘记了数组 $$$a$$$ 是什么样子的。突然,他想到从数组 $$$b$$$ 恢复数组 $$$a$$$ 将是一个有趣的问题(不幸的是,不是 A)。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 140582$$$) — 数组 $$$a$$$ 的长度。

第二行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_{n}$$$ ($$$0 \le b_i \le 187126$$$)。

输出

如果可以恢复某个长度为 $$$n$$$ 的数组 $$$a$$$,使得 $$$b_i = a_i \mod a_{(i \mod n) + 1}$$$ 对所有 $$$i = 1, 2, \ldots, n$$$ 成立,在第一行打印“YES”以及整数 $$$a_1, a_2, \ldots,第二行中的 a_n$$$。所有 $$$a_i$$$ 应满足 $$$1 \le a_i \le 10^{18}$$$。我们可以证明,如果存在答案,那么具有这种约束的答案也存在。

不可能恢复任何有效的$$$a$$$,在一行中打印“NO”。

您可以以任何大小写(大写或小写)打印每个字母。

示例

输入 #1

4
1 3 1 0

输出 #1

YES
1 3 5 2

输入 #2

2
4 4

输出 #2

NO

注意

在第一个示例中:

- $$$1 \mod 3 = 1$$$
- $$$3 \mod 5 = 3$$$
- $$$5 \mod 2 = 1$$$
- $$$2 \mod 1 = 0$$$