Сирна пастка#12998

Сирна пастка

2 секунди
512 мегабайтів
Дуже складна

Том вирішив підготувати хитру пастку для Джеррі. Він розклав шматочків сиру по колу. Кожен шматочок приносить Джеррі певне задоволення a_i — воно може бути навіть від’ємним, якщо Джеррі не любить цей вид сиру.

Том ще не визначив точні значення a_i, але він чудово знає поведінку Джеррі: якщо першим доступним шматочком буде -й, то Джеррі почне їсти за годинниковою стрілкою, з’ївши деякий (можливо, порожній) префікс цієї лінійної послідовності так, щоб максимізувати сумарне задоволення.

Нехай позначає максимальну суму елементів деякого (можливо, порожнього) префікса масиву .

Для кожного визначимо послідовність b_i як циклічний зсув масиву , що починається з його -го елемента:

b_i = [a_i, a_{i + 1}, \dots, a_n, a_1, \dots, a_{i - 1}],

тобто b_1 = a.

Відомо, що якщо першим доступним шматочком є -й, то сумарне задоволення Джеррі дорівнюватиме c_i = mx(b_i).

Єдине, що Том уже визначив, — це масив . Допоможіть йому знайти будь-який масив , для якого масив можна отримати відповідно до описаного вище правила.

Вхідні дані

У першому рядку задано ціле число — довжина масиву .

У другому рядку задано цілих чисел c_1, c_2, \dots, c_n — елементи масиву .

1 \le n \le 2 \cdot 10^5,

0 \le c_i \le 10^{12}.

Вихідні дані

Виведіть будь-який масив , для якого |a_i| \le 10^{18}, такий, що масив можна отримати з нього відповідно до умови.

Якщо існує декілька правильних відповідей, виведіть будь-яку з них.

Можна довести, що за наведених обмежень завжди існує принаймні один масив , який задовольняє умову.

Приклади

Приклад

Loading
Loading

Приклад 1

Loading
Loading