A. 爱丽丝与书

每次测试时间限制：$1$ 秒 每次测试内存限制：$256$ 兆字节

爱丽丝有 $n$ 本书。第 $1$ 本书有 $a_1$ 页，第 $2$ 本书有 $a_2$ 页，……，第 $n$ 本书有 $a_n$ 页。爱丽丝执行如下操作：

她将所有书分成两堆非空的书堆，每本书恰好属于其中一堆。 爱丽丝阅读每一堆中编号最大的那一本书。

爱丽丝非常喜欢阅读，请你帮她求出：将书分成两堆后，她能阅读的最大总页数。

输入

每组测试包含多个测试用例。 第一行输入一个整数 $t$（$1 \le t \le 500$），表示测试用例的数量。

每个测试用例的第一行输入一个整数 $n$（$2 \le n \le 100$），表示书的数量。

每个测试用例的第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1 \le a_i \le 10^9$），表示每本书的页数。

输出

对于每个测试用例，输出一个整数，表示爱丽丝能阅读的最大总页数。

样例输入

$5$ $2$ $1$ $1$ $4$ $2$ $3$ $3$ $1$ $5$ $2$ $2$ $3$ $2$ $2$ $2$ $10$ $3$ $3$ $1$ $2$ $3$

样例输出

$2$ $4$ $5$ $13$ $5$

说明

在第一个测试用例中，爱丽丝可以将第 $1$ 本书放入第一堆，第 $2$ 本书放入第二堆，此时她会阅读 $a_1+a_2=1+1=2$ 页。

在第二个测试用例中，爱丽丝可以将编号为 $2$、$3$ 的书放入第一堆，编号为 $1$、$4$ 的书放入第二堆。她会阅读第一堆中编号最大的书 $3$，第二堆中编号最大的书 $4$，总共阅读 $a_3+a_4=3+1=4$ 页。 核心思路（基于标程） 关键结论：无论怎么分书，编号为 n 的书一定会被读到。因为编号 n 是所有书里最大的，它所在的那一堆，最高编号必然是 n，所以这本书一定会被选中阅读。 基于这个结论，我们只需要做两件事：

固定选择最后一本书 an​； 在前 n−1 本书中找到页数最多的那一本 ak​（k<n）； 两者相加就是答案。