Uyğun düzülüş#13121

Uyğun düzülüş

2 saniyə
256 meqabayt

tam ədəddən ibarət massivi verilir.

Elementlərin yerini elə dəyişməyin mümkün olub-olmadığını müəyyən edin ki, alınan massivində hər 1\le i\le n üçün

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

şərti ödənsin. Mümkündürsə, belə bir düzülüş tapın.

Giriş

Birinci sətirdə bir tam ədəd (1\le t\le10^4) — test hallarının sayı verilir.

Hər test halının birinci sətrində bir tam ədəd (1\le n\le10^5) — massivin uzunluğu verilir.

İkinci sətirdə tam ədəd a_1,a_2,\ldots,a_n (-10^9\le a_i\le10^9) verilir.

Bütün test halları üzrə qiymətlərinin cəmi 10^5-i keçmir.

Çıxış

Hər test halı üçün uyğun düzülüş yoxdursa, NO çap edin.

Əks halda, YES, növbəti sətirdə isə alınan massivin elementini çap edin. Bir neçə uyğun düzülüş varsa, onlardan istənilən birini çap edin.

YES və NO cavablarında böyük və kiçik hərflərdən istənilən şəkildə istifadə edə bilərsiniz.

Nümunələr

Nümunə 1

Loading
Loading

Nümunə 2

Loading
Loading

Nümunə 3

Loading
Loading

Qeyd

Birinci nümunənin birinci test halında [2,0,-1,-10,-7,8] düzülüşünün prefiks cəmləri 2,2,1,-9,-16,-8, prefiks maksimumları isə 2,2,2,2,2,8 olur. Bütün bərabərsizliklər ödənir. İkinci test halında uyğun düzülüş yoxdur.

İkinci nümunədə bir elementli massiv həmişə şərti ödəyir. Sıfırlardan ibarət massiv də uyğundur. Lakin massivi üçün bütün elementlərin cəmi -dir və maksimum element -dən böyükdür.

Bal hesablama

  1. Alt tapşırıq ( bal): t\le10, n\le10.

  2. Alt tapşırıq ( bal): n\le100.

  3. Alt tapşırıq ( bal): əlavə məhdudiyyət yoxdur.