Ball — Eolymp

Input

Birinchi qatorda bitta butun son $t$ ( $1 \leq t \leq 1 0^{4}$ 1 \le t \le 10^4) — test hollari soni.

Har bir test holining birinchi qatorida bitta butun son $n$ ( $1 \leq n \leq 5 \cdot 1 0^{5}$ 1 \le n \le 5 \cdot 10^5) — massivning uzunligi.

Har bir test holining ikkinchi qatorida $n$ ta butun son $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \dots, a_n ( $- 1 0^{9} \leq a_{i} \leq 1 0^{9}$ -10^9 \le a_i \le 10^9) — massiv elementlari.

$n$ yig'indisi $5 \cdot 1 0^{5}$ 5 \cdot 10^5 dan oshmasligi kafolatlanadi.

Output

Har bir test holi uchun massivning umumiy $ball$ ini chiqarish.

Examples

Example 1

Loading

Note

Birinchi test holi uchun:

Masalan, agar $a = [1, 2, 3]$ a=[1,2,3] bo'lsa, $ball$ quyidagicha hisoblanadi:

$[1, 2, 3] \to 1 < 5 - 1 - 1$ [\mathbf{1},2,3] \rightarrow 1 < 5 \xrightarrow{-1} -1
$[1, 2, 3] \to 2 < 4 - 1 - 2$ [1,\mathbf{2},3] \rightarrow 2 < 4 \xrightarrow{-1} -2
$[1, 2, 3] \to 3 = 331$ [1,2,\mathbf{3}] \rightarrow 3 = 3 \xrightarrow{3} 1
$[1, 2, 3] \to 3 = 334$ [\mathbf{1,2},3] \rightarrow 3 = 3 \xrightarrow{3} 4
$[1, 2, 3] \to 5 > 126$ [1,\mathbf{2,3}] \rightarrow 5 > 1 \xrightarrow{2} 6
$[1, 2, 3] \to 6 > 028$ [\mathbf{1,2,3}] \rightarrow 6 > 0 \xrightarrow{2} 8

Shunday qilib, massivning umumiy $ball$ i $- 1 - 1 + 3 + 3 + 2 + 2 = 8$ -1 - 1 + 3 + 3 + 2 + 2 = 8 ga teng, esda tutingki, to'liq massivni segment sifatida hisoblaganda qolgan sonlarning yig'indisi 0.

Ikkinchi test holida uchta subsegment mavjud: $[1]$ , $[- 1]$ , $[1, - 1]$ , bu ajoyib, oddiy va mukammal bilan mos keladi, balli $2 + 3 - 1 = 4$ 2+3-1=4.

Scoring

( $5$ ball) : $a_{i} = 1 (1 \leq i \leq n)$ a_i=1 (1 \le i \le n)
( $10$ ball) : $(1 \leq \sum n \leq 100)$ (1 \le \sum n \le 100)
( $20$ ball) : $(1 \leq \sum n \leq 2000)$ (1 \le \sum n \le 2000)
( $25$ ball) : $(1 \leq \sum n \leq 2 \cdot 1 0^{5})$ (1 \le \sum n \le 2 \cdot 10^5)
( $50$ ball) : $(0 \leq a_{i} \leq 1 0^{9})$ (0 \le a_i \le 10^9)
( $50$ ball) : $(0 \leq \sum_{i = 1}^{n} ∣ a_{i} ∣ \leq 1 0^{9})$ (0 \le \sum_{i=1}^n |a_i| \le 10^9)
( $75$ ball) : hech qanday qo'shimcha cheklovlar yo'q