Eat The Candy

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

题目描述

$\hspace{15pt}$ 小苯有 $n$ 个盒子排成一排，第 $i$ 个盒子里有 $a_i$ 颗糖。小苯可以进行以下操作任意多次：
$\hspace{23pt}\bullet\,$ 选择两个相邻的非空的盒子 $i$ 和 $i+1$ （即 $a_i > 0$ 且 $a_{i+1} > 0$ ），从每个盒子中各吃掉一颗糖，然后额外得到一颗新糖放入任意一个盒子（可以是这 $n$ 个盒子中的任意一个）。

$\hspace{15pt}$ 你的任务就是以最优方案操作，以最大化最终装糖果最多的盒子中的糖果数量，并将其输出。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行输入一个整数 ，表示盒子的个数。
第二行输入  个非负整数 ，表示每个盒子中的初始糖数。

除此之外，保证所有测试数据的  之和不超过 。

输出描述:

对于每组数据，新起一行输出一个整数，表示最优情况下，所装糖果最多的一盒糖果中糖果数量的最大值。

示例1

输入

复制

输出

复制

4
1
5

说明

对于第一组测试数据，选择盒子  和 ，各取  颗，得到  颗新糖放入盒子 ，变为 ，此时最大值达到 ，最优。