Restore Array

2000ms

262144K

Description:

While discussing a proper problem A for a Codeforces Round, Kostya created a cyclic array of positive integers $$$a_1, a_2, \ldots, a_n$$$. Since the talk was long and not promising, Kostya created a new cyclic array $$$b_1, b_2, \ldots, b_{n}$$$ so that $$$b_i = (a_i \mod a_{i + 1})$$$, where we take $$$a_{n+1} = a_1$$$. Here $$$mod$$$ is the modulo operation. When the talk became interesting, Kostya completely forgot how array $$$a$$$ had looked like. Suddenly, he thought that restoring array $$$a$$$ from array $$$b$$$ would be an interesting problem (unfortunately, not A).

Input:

The first line contains a single integer $$$n$$$ ($$$2 \le n \le 140582$$$) — the length of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_{n}$$$ ($$$0 \le b_i \le 187126$$$).

Output:

If it is possible to restore some array $$$a$$$ of length $$$n$$$ so that $$$b_i = a_i \mod a_{(i \mod n) + 1}$$$ holds for all $$$i = 1, 2, \ldots, n$$$, print «YES» in the first line and the integers $$$a_1, a_2, \ldots, a_n$$$ in the second line. All $$$a_i$$$ should satisfy $$$1 \le a_i \le 10^{18}$$$. We can show that if an answer exists, then an answer with such constraint exists as well.

It it impossible to restore any valid $$$a$$$, print «NO» in one line.

You can print each letter in any case (upper or lower).

Sample Input:

4
1 3 1 0

Sample Output:

YES
1 3 5 2

Sample Input:

2
4 4

Sample Output:

NO

Note:

In the first example:

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

Informação

Provedor Codeforces

Código CF1028E