Tullanma səyahətinin xalı

Giriş

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

Hər test halının birinci sətrində bir tam ədəd $n$ ( $1 \leq n \leq 4 \cdot 1 0^{5}$ 1 \le n \le 4 \cdot 10^5) — $a$ massivinin uzunluğu verilir.

Hər test halının ikinci sətrində $n$ tam ədəd $a_{1}, a_{2}, ..., 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) — $a$ massivi verilir.

Bütün test halları üzrə $n$ cəminin $4 \cdot 1 0^{5}$ 4 \cdot 10^5-i aşmayacağı təmin edilir.

Çıxış

Hər test halı üçün bir tam ədəd — əldə edə biləcəyiniz maksimal xalı çıxarın.

Nümunələr

Nümunə 1

Loading

Qeyd

Birinci test halında bütün elementləri əlavə etmək optimaldır, buna görə də yekun xal $1 + 2 + 3 + 4 + 5 = 15$ 1 + 2 + 3 + 4 + 5 = 15 olur.

İkinci test halında aşağıdakıları edə bilərsiniz:

$i = 1$ i=1, xala $10$ əlavə edin və $i = 2$ i=2-yə keçin.

$i = 2$ i=2, $d = 3$ d=3 seçin, $i = 5$ i = 5-ə tullanın və səyahəti bitirin.

Beləliklə, yekun xal $10$ olur.

Bal hesablama

Altməsələ $1$ ( $10$ bal): bütün $i$ üçün ( $1 \leq i \leq n$ 1 \le i \le n) $0 \leq a_{i}$ 0 \le a_i.
Altməsələ $2$ ( $10$ bal): $\sum n \leq 20$ \sum n \le 20.
Altməsələ $3$ ( $30$ bal): $\sum n \leq 5000$ \sum n \le 5000.
Altməsələ $4$ ( $50$ bal): Əlavə məhdudiyyət yoxdur.