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

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

0.2 seconds
256 megabytes
Easy

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

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

Input

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

Output

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

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

  • b_i \le b_{i+1};

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

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Scoring

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

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

  2. ( балів): N \le 1\,000; 0 \le a_i;

  3. ( балів): N \le 1\,000; a_i \le 0;

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