时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
演员Jakon喜欢在群里呼风唤雨。
从而召唤出一阵阵的风和雨，导致每次Eriktse不得不在群里打伞。
众所周知，先有风后有雨。
现在空中有N股神秘力量，它们要么是“风”，要么是“雨”，且“雨”一定在“风”的后面，且不会出现“只有风”或“只有雨”的情况。
换句话说，若把神秘力量从1到N编号，则存在一个分界点K使得
全是风，
全是雨。(
)
每一股神秘力量有一个初始能量
，如果将这份力量看作“风”，则这一股的真实能量为
，如果看作“雨”，则这一股真实能量为
。
Eriktse的伞的1点防护值可以挡住1的能量。
能量和为所有神秘力量的真实能量之和，求Eriktse的伞至少需要多少防护值
)才能抵挡住Jakon的风雨。
从而召唤出一阵阵的风和雨，导致每次Eriktse不得不在群里打伞。
众所周知，先有风后有雨。
现在空中有N股神秘力量，它们要么是“风”，要么是“雨”，且“雨”一定在“风”的后面，且不会出现“只有风”或“只有雨”的情况。
换句话说，若把神秘力量从1到N编号，则存在一个分界点K使得
每一股神秘力量有一个初始能量
Eriktse的伞的1点防护值可以挡住1的能量。
能量和为所有神秘力量的真实能量之和，求Eriktse的伞至少需要多少防护值
输入描述:
有多组测试样例。
第一行一个整数T，表示测试样例数量()。
一个整数N，表示神秘力量的股数()。
接下来N个整数，表示第i股神秘力量的初始能量ai ()
输出描述:
对于每一个测试用例，输出一个整数表示Eriktse的伞需要的最小防护值
备注:
对于样例中第一组，令k = 2，可以得到最大能量114 * (2 - 9) + 514 * (3 + 7 + 5) = 6912