Кожен елемент можна залишити як є або змінити йому знак, тобто для позиції доступні рівно два значення: |a_i| та -|a_i|. Замінимо одразу всі числа на модулі — це нічого не змінює, зате спрощує міркування.
Тепер працює жадібний підхід: ідемо зліва направо і на кожній позиції беремо найменше допустиме значення, яке не менше за попереднє. Чим менше поточне число, тим більше свободи залишиться далі, тому такий вибір ніколи не шкодить.
Конкретно, нехай — значення, обране на попередній позиції. Для поточної позиції:
якщо -|a_i| \ge p, беремо -|a_i| — це менший із двох варіантів;
інакше, якщо |a_i| \ge p, беремо |a_i|;
інакше обидва варіанти менші за , послідовність побудувати неможливо — виводимо NO.
Для першого елемента попереднього значення немає, тому одразу беремо -|a_1| як найменше можливе.
Якщо дійшли до кінця, виводимо YES і сам масив. Складність — , чого достатньо при N \le 100\,000.
Зверніть увагу, що жадібність тут коректна саме тому, що вибір на позиції впливає на майбутнє лише через одне число — обране значення.