Нехай у нас всі числа додатні. Тоді ми можемо за $$$n-1$$$ операцію розв'язати задачу: до другого числа додамо перше, до третього друге, і так далі. Таким чином $$$i$$$-те число — це сума перших $$$i$$$ чисел. Оскільки всі числа додатні, то новий масив буде зростати.
Нехай у нас всі числа від'ємні. Будемо робити це саме, але навпаки. До передостаннього числа додамо останнє, до третього числа з кінця, додамо друге число з кінця, і так далі.
Якщо ж у нас є як і від'ємні числа, так і додатні, то знайдемо максимальне і мінімальне число. Нехай $$$m_1$$$ — максимальне число, а $$$m_2$$$ — мінімальне.
Якщо $$$m_1 \geq |m_2|$$$, то ми можемо до всіх чисел, крім $$$m_1$$$, додати $$$m_1$$$. Це зробить всі числа додатніми. Для цього нам потрібно рівно $$$n-1$$$. А таку задачу ми вже вміємо розв'язувати за $$$n-1$$$.
Якщо ж $$$m_1 < |m_2|$$$, то до всіх чисел, крім $$$m_2$$$, додамо $$$m_2$$$. Всі числа вийдуть від'ємними. Таку задачу також вміємо розв'язувати.