E. Восстановление массива
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Обсуждая подходящую задачу A для раунда на Codeforces, Костя создал циклический массив из целых положительных чисел $$$a_1, a_2, \ldots, a_n$$$. Так как разговор затянулся, Костя создал новый циклический массив $$$b_1, b_2, \ldots, b_{n}$$$ такой, что $$$b_i = (a_i \mod a_{i + 1})$$$, где мы считаем $$$a_{n+1} = a_1$$$. Под $$$mod$$$ имеется ввиду остаток от деления. Когда разговор стал интересным, Костя абсолютно забыл массив $$$a$$$. Вдруг он подумал, что восстановление массива $$$a$$$ из массива $$$b$$$ может быть интересной задачей (к сожалению, не A).

Входные данные

В первой строке записано одно целое число $$$n$$$ ($$$2 \le n \le 140582$$$) — длина массива $$$a$$$.

Во второй строке записано $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_{n}$$$ ($$$0 \le b_i \le 187126$$$).

Выходные данные

Если возможно восстановить некоторый массив $$$a$$$ длины $$$n$$$ такой, что $$$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» в первой строчке.

Вы можете выводить каждую букву в любом регистре: заглавной или строчной.

Примеры
Входные данные
4
1 3 1 0
Выходные данные
YES
1 3 5 2
Входные данные
2
4 4
Выходные данные
NO
Примечание

В первом примере:

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