Коригування масивів

Голова журі олімпіади згенерував декілька числових масивів, які будуть вхідними даними для цікавої задачі. Але ці масиви йому не подобаються, тому що вони не відсортовані! Сортувати ці масиви голова журі не хоче. Єдине що він збирається робити $-$ трішки відкоригувати масиви, змінюючи знаки у деяких. Іншими словами, можна робити дуже просту операцію: деякі елементи $a_i$ замінити на $-a_i$.

Напишіть програму, яка з'ясує, чи зможе голова журі за допомогою описаної операції зробити масив відсортованим за неспаданням.

Вхідні дані

У першому рядку вхідних даних дано ціле число $N$ $-$ кількість елементів у масиві ($1\le N\le 100000$). У наступному рядку дано $n$ цілих чисел $a_i$ $-$ масив, який голова журі олімпіади хоче зробити відсортованим за неспаданням ($|a_i|\le 100000$).

Вихідні дані

Якщо не можна замінити деякі елементи $a_i$ на $-a_i$, так щоб масив став відсортованим за неспаданням, виведіть «NO».

Інакше, у першому рядку виведіть «YES». У другому рядку виведіть $N$ чисел $b_i$ $-$ масив, для всіх елементів якого виконується:

• $b_i\le b_{i+1}$;

• $b_i=a_i$ або $b_i=-a_i$.

Приклади

Оцінювання

У цієї задачі є чотири підзадачі, для яких виконуються додаткові обмеження, вказані в таблиці нижче. Бали за кожну підзадачу нараховуються тільки у випадку, якщо пройдено всі тести цієї підзадачі, а також всі тести всіх необхідних підзадач. Номери необхідних підзадач також вказані в таблиці.

1. ($20$ балів): $N\le 20$;

2. ($25$ балів): $N\le 1000$; $0\le a_i$;

3. ($25$ балів): $N\le 1000$; $a_i\le 0$;

4. ($30$ балів): немає додаткових обмежень;