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: VERY_HARD
Tags: Constructive algorithms

Starter code:

Solutions:
n = int(input())
b = []
b = [int(el) for el in input().split()]
n = len(b)
i = n - 1
while b[i - 1] >= b[i] and i > 0:
	i = i - 1
if i == 0 and b[0] == b[n - 1]:
	if b[0] != 0:
		print('NO')
		raise SystemExit()
	else:
		print('YES')
		print(' '.join((str(1) for i in range(n))))
		raise SystemExit()
else:
	k = i + 1
b.insert(0, b[n - 1])
a = [None for i in range(n + 1)]
a[k] = b[k]
for i in range(k - 1, 0, -1):
	a[i] = b[i] + a[i + 1]
	while a[i] <= b[i - 1]:
		a[i] = a[i] + a[i + 1]
i = b.pop(0)
i = a.pop(0)
if k == n:
	print('YES')
	print(' '.join((str(a[i]) for i in range(n))))
	raise SystemExit()
a[n - 1] = a[0] + b[n - 1]
while a[n - 1] <= b[n - 2]:
	a[n - 1] = a[n - 1] + a[0]
i = n - 2
while a[i] == None:
	a[i] = b[i] + a[i + 1]
	while a[i] <= b[i - 1]:
		a[i] = a[i] + a[i + 1]
	i = i - 1
if k <= n - 2 and a[k] <= a[k + 1]:
	a[k] = a[k] + a[k + 1]
if k == n - 1 and a[k] <= a[0]:
	a[k] = a[k] + a[0]
print('YES')
print(' '.join((str(a[i]) for i in range(n))))


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)


n = int(input())
b = list(map(int, input().split()))
answer = [-100] * n
for i in range(n):
	if b[i - 1] < b[i]:
		start_idx = i
		break
else:
	if b[0] == 0:
		print('YES')
		print('1 ' * n)
	else:
		print('NO')
	exit()
answer[start_idx] = b[start_idx]
current_idx = start_idx - 1
if current_idx < 0:
	current_idx += n
while current_idx != start_idx:
	(b_next, b_curr) = (b[current_idx - 1], b[current_idx])
	a_prev = answer[(current_idx + 1) % n]
	k_curr = (b_next - b_curr + a_prev) // a_prev
	answer[current_idx] = a_prev * k_curr + b_curr
	current_idx -= 1
	if current_idx < 0:
		current_idx += n
print('YES')
print(' '.join(map(str, answer)))


n = int(input())
b = list(map(int, input().split()))
pos = [i for i in range(n) if b[i] > b[i - 1]]
a = None
if pos:
	x = pos[0]
	a = [0] * n
	a[x] = b[x]
	i = (x - 1) % n
	while i != x:
		if b[i - 1] < b[i]:
			a[i] = b[i]
		else:
			nxt = a[(i + 1) % n]
			a[i] = b[i] + nxt * ((b[i - 1] - b[i]) // nxt + 1)
		i = (i - 1) % n
elif b[0] == 0:
	a = [1] * n
if a:
	print('YES')
	print(*a)
else:
	print('NO')


import math
import sys
input = sys.stdin.readline
n = int(input())
a = [int(_) for _ in input().split()]
piv = -1
for i in range(n):
	if a[i - 1] < a[i]:
		piv = i
		break
if min(a) == 0 and max(a) == 0:
	print('YES')
	print(' '.join(['1'] * n))
	exit(0)
elif piv == -1:
	print('NO')
	exit(0)
for i in range(n):
	prv = (n + piv - i + 1) % n
	cur = (n + piv - i) % n
	nxt = (n + piv - i - 1) % n
	if a[nxt] >= a[cur]:
		a[cur] += ((a[nxt] - a[cur]) // a[prv] + 1) * a[prv]
print('YES')
print(' '.join(map(str, a)))


from sys import stdin
n = int(stdin.readline())
b = [int(x) for x in stdin.readline().strip().split()]
start = -1
a = [0] * n
for i in range(n):
	if b[i] < b[(i + 1) % n]:
		start = (i + 1) % n
		break
if max(b) == 0:
	print('YES')
	print(' '.join(['123'] * n))
	exit()
if start == -1:
	print('NO')
	exit()
cnt = 0
prev = start
a[start] = b[start]
while cnt < n:
	next = (prev - 1 + n) % n
	if b[next] == 0:
		a[next] = a[prev]
	else:
		a[next] = b[next]
		if b[next] >= a[prev]:
			prevprev = (prev + 1) % n
			q = (b[next] - a[prev]) // a[prevprev] + 1
			a[prev] += a[prevprev] * q
	prev = next
	cnt += 1
print('YES')
print(' '.join([str(x) for x in a]))
for i in range(n):
	if b[i] != a[i] % a[(i + 1) % n]:
		raise Exception('fail')


maxN = int(200000.0 + 10)
n = 0
b = [0] * maxN
ans = [0] * maxN
n = int(input())
inp = input().split()
flag = False
for i in range(1, n + 1):
	b[i] = int(inp[i - 1])
	if i > 1 and b[i] != b[i - 1]:
		flag = True
b[0] = b[n]
b[n + 1] = b[1]
if flag == False:
	if b[1] != 0:
		print('NO')
	else:
		print('YES')
		for i in range(1, n + 1):
			print(1)
	exit()
print('YES')
pos = -1
mx = -1
for i in range(1, n + 1):
	if b[i] >= mx:
		mx = b[i]
		if b[i] != b[i - 1]:
			pos = i
ans[pos] = mx
tmp = pos - 1
sum = mx
if tmp == 0:
	tmp = n
while tmp != pos:
	sum += b[tmp]
	ans[tmp] = sum + mx
	tmp -= 1
	if tmp == 0:
		tmp = n
for i in range(1, n + 1):
	print(ans[i])


n = int(input())
b = list(map(int, input().split()))
pos = [i for i in range(n) if b[i] > b[i - 1]]
if not pos:
	if b[0] == 0:
		a = [1] * n
		print('YES')
		print(*a)
	else:
		print('NO')
else:
	x = pos[0]
	a = [0] * n
	a[x] = b[x]
	cur = b[x]
	i = x - 1
	while i % n != x % n:
		i %= n
		p = b[i - 1]
		if p < b[i]:
			a[i] = b[i]
		else:
			p -= b[i]
			zz = cur * (p // cur)
			zz += cur
			a[i] = zz + b[i]
		cur = a[i]
		i -= 1
	print('YES')
	print(*a)