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).


-----Examples-----
Input
4
1 3 1 0

Output
YES
1 3 5 2

Input
2
4 4

Output
NO



-----Note-----

In the first example:  $1 \mod 3 = 1$  $3 \mod 5 = 3$  $5 \mod 2 = 1$  $2 \mod 1 = 0$

Difficulty: competition

Starter code:

Solutions:
n = int(input())

b = list(map(int, input().split()))

m, M = min(b), max(b)
if m == M:
    if M == 0:
        print('YES')
        print(' '.join(['1' for i in range(n)]))
    else:
        print('NO')
else:
    print('YES')

    pos = list([i for i in range(n) if b[i] == M and b[i - 1] < M])[0]

    a = [0 for i in range(n)]

    a[pos] = M
    a[pos - 1] = (M << 1) + b[pos - 1]

    for i in range(2, n):
        a[pos - i] = a[pos - i + 1] + b[pos - i]

    print(*a)