Mảng không giảm

Cho mảng \(a\) gồm \(n\) số nguyên \(a_1, a_2, \dots, a_n\). Bạn có thể thay thế một số phần tử \(a_i\) của mảng bằng \(-a_i\) để mảng trở thành mảng không giảm, hoặc cho biết điều này là không thể.

Mảng \(b_1, b_2, \dots, b_n\) được gọi là mảng không giảm nếu \(b_1 \le b_2 \le \dots \le b_n\).

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \le n \le 10^5)\) là số phần tử của mảng \(a\).

• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) \((-10^9 \le a_i \le 10^9)\) là các phần tử của mảng \(a\).

Output

• Nếu không thể làm cho mảng không giảm, ghi ra No.

• Ngược lại ghi ra hai dòng: dòng đầu tiên ghi Yes, dòng thứ hai ghi \(b_1, b_2, \dots, b_n\) là một mảng không giảm với \(b_i = a_i\) hoặc \(b_i = -a_i\) với mọi \(1 \le i \le n\).

• Nếu có nhiều mảng \(b\) thỏa mãn, hãy ghi ra mảng có thứ tự từ điển nhỏ nhất (so sánh \(b_1\) trước, nếu bằng nhau thì so sánh \(b_2\), \dots). Số phép thay thế không cần tối thiểu.

Notes

Với \(a = (1, -1, -2, 3, 6)\): đáp án là Yes và mảng \(b = (-1, -1, 2, 3, 6)\).

Với \(a = (3, 1, 2)\): không có cách nào, đáp án là No.

Với \(a = (1, 2, 3)\): đáp án là Yes và \(b = (-1, 2, 3)\).

Scoring

• Có \(25\%\) số test thỏa mãn \(n \le 20\);

• \(25\%\) số test khác thỏa mãn \(n \le 1000\);

• \(50\%\) số test còn lại không có ràng buộc gì thêm.