Çətin Oyun — Eolymp

Giriş

Birinci sətir bir tam ədəd $t$ $(1 \leq t \leq 1 0^{4})$ (1 \le t \le 10^4) — test hallarının sayı.

Hər bir test halı iki sətirdən ibarətdir:

Birinci sətir bir tam ədəd $n (1 \leq n \leq 2 \cdot 1 0^{5})$ n(1 \le n \le 2 \cdot 10^5) — massivinin uzunluğu.

İkinci sətir $n$ tam ədəd $a_{1}, a_{2}, \dots, a_{n}$ a_{1},a_{2},…,a_{n} $(- 1 0^{9} \leq a_{i} \leq 1 0^{9})$ (-10^9 \le a_{i} \le 10^9) — onun hər raunddan sonra qazanacağı xallar.

Bütün test hallarının $n$ cəminin $2 \cdot 1 0^{5}$ 2 \cdot 10^5-dən çox olmayacağı təmin edilir.

Çıxış

Hər bir test halı üçün, Fateh-in əldə etdiyi maksimum ümumi xal dəyərini əldə edən massiv $a$ -nın istənilən permutasiyasını çıxarın — $b_{1}, b_{2}, b_{3}, ..., b_{n}$ b_1,b_2,b_3,...,b_n.

Belə bir permutasiya yoxdursa, $- 1$ çıxarın.

Nümunələr

Nümunə 1

Loading

Qeyd

Birinci test halının nəticəsi aşağıdakı kimidir:

Fateh $5$ xal alır, Ümumi $5$ xal.
Fateh $3$ xal alır, Ümumi $8$ xal.
Fateh $2$ xal alır, Ümumi $10$ xal.
Fateh $- 1$ xal alır, O, əsəbiləşir və $9$ xalı var, indi növbəti iki oyunu atlayacaq və heç bir oyun qalmadığı üçün daha oynaya bilmir.

Onun qazandığı maksimum xal $9$ -dur.

Bal hesablama

Alt tapşırıq $1$ ( $20$ xal) : $(1 \leq n \leq 8)$ (1 \le n \le 8) və $(1 \leq t \leq 100)$ (1 \le t \le 100)
Alt tapşırıq $2$ ( $30$ xal) : $(0 \leq a_{i} \leq 1 0^{9})$ (0 \le a_i \le 10^9)
Alt tapşırıq $3$ ( $150$ xal) : Əlavə məhdudiyyət yoxdur