该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给出一个长度为 $n$ 的序列 $a$，选出其中连续且非空的一段使得这段和最大。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量$t(1≤t≤1000)$。

每个测试用例的第一行都包含一个整数$n$， 表示序列$a$的长度。$(1≤n≤2 \cdot 10^5)$

每个测试用例的第二行都包含$n$个整数$a_1，a_2，...，a_n （−10 ^4≤a_i≤10 ^4 ）$，表示给定的序列$a$。

每个测试$n$的总和不超过$2 \cdot 10^{5}$。

输出格式

对于每个测试用例，输出一个整数表示答案。（每个测试用例结尾必须输出一个换行符）

样例

2
7
2 -4 3 -1 2 -4 3
6
1 2 3 4 5 6

4
21

样例解释

对于第一组样例：

选取 $[2,4]$ 子段 {$3,−1,2$}，其和为 $4$，输出$4$。

对于第二组样例：

选取 $[0,5]$ 子段 {$1，2，3，4，5，6$}，其和为 $21$，输出$21$。