Потрібна перестановка#13121

Потрібна перестановка

2 секунди
256 мегабайтів

Задано масив з цілих чисел.

Визначте, чи можна переставити його елементи так, щоб в отриманому масиві для кожного 1\le i\le n виконувалось

\sum_{j=1}^{i}b_j\le\max(b_1,b_2,\ldots,b_i).

Якщо це можливо, знайдіть будь-яку таку перестановку.

Вхідні дані

Перший рядок містить ціле число (1\le t\le10^4) — кількість наборів вхідних даних.

Перший рядок кожного набору містить ціле число (1\le n\le10^5) — кількість елементів масиву.

Другий рядок містить цілих чисел a_1,a_2,\ldots,a_n (-10^9\le a_i\le10^9).

Гарантується, що сума за всіма наборами вхідних даних не перевищує 10^5.

Вихідні дані

Для кожного набору вхідних даних виведіть NO, якщо потрібної перестановки не існує.

Інакше виведіть YES, а в наступному рядку — елементів отриманого масиву. Якщо підходять кілька перестановок, виведіть будь-яку з них.

Літери у відповідях YES та NO можна виводити в будь-якому регістрі.

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Приклад 3

Loading
Loading

Примітка

У першому наборі першого прикладу для перестановки [2,0,-1,-10,-7,8] суми префіксів дорівнюють 2,2,1,-9,-16,-8, а максимуми — 2,2,2,2,2,8. Усі нерівності виконуються. У другому наборі потрібної перестановки не існує.

У другому прикладі масив з одного елемента завжди задовольняє умову. Масив з нулів також підходить, а для сума всього масиву дорівнює і перевищує його максимум .

Оцінювання

  1. Підзадача ( балів): t\le10, n\le10.

  2. Підзадача ( балів): n\le100.

  3. Підзадача ( балів): без додаткових обмежень.