禅

题号：NC232732
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

骑士？只是我手上的傀儡而已，冲锋！

本题请格外注意标红和加粗的字！

你是一个骑士，现有一个包含 $N$ 个格子的一维棋盘（一行 $N$ 列）。

第 $i$ 个格子有一个战斗力为 $a_i$ 的怪物：所有怪物对应的 $a_i>0$ ，若 $a_i=0$ 表示第 $i$ 列是公主。

你的任务目标是营救被困于该格的公主（走到公主所在的格子），你需要选择一个 公主不在 的格子作为起点，任意时刻不重复经过已经走过的点。

到达某个格子时，必须与当前怪物战斗，如果战斗力严格大于其战斗力，可以击败它并获得它所具有的全部战斗力。

形式化地，设你的战斗力是 $m$ ，怪物的战斗力是 $a_i$ ：

$\text{战斗}\begin{cases}m\le a_i\rightarrow\text{任务失败}\\m> a_i\rightarrow\text{击败该怪物，且}~m\leftarrow m+a_i\end{cases}$

给定序列 $\{a_n\}$ ，求采用最优策略选择起点及行动路径时最少的初始战斗力 $m_0$ 使得能完成任务目标。

输入描述:

全文第一行输入一个正整数 ，表示数据组数。

对于每组数据，第一行输入一个正整数 。

第二行输入  个整数，第  个表示 。

数据保证存在且仅存在一个  满足 。

输出描述:

对于每组数据，输出一行一个整数表示  的最小值，无解时输出一行字符串 。

示例1

输入

复制

输出

复制

2
5

说明

所有的样例均从第一个格子开始遍历，一路向右即可。