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

时间限制：1000ms

空间限制：512MB

问题描述

坏蛋熊梦要破坏地球，梦梦和熊熊需要合力打败他才能维护世界的和平。

熊梦在 $n$ 个城市均放置了黑魔法，这 $n$ 个城市恰好排成了一条直线，编号为 $1$ 到 $n$，其中第 $i$ 个城市的黑魔法值为 $a_i$，白魔法值为 $0$。

当存在一个城市的黑魔法值大于白魔法值时，地球就会毁灭。

你可以指定给梦梦一个参数 $x \in [1,n]$，梦梦会将编号为 $1,2,…,x$ 的城市白魔法值加 $1$，这一操作会消耗梦梦 $x$ 点能量。

你可以指定给熊熊一个参数 $x \in [1,n]$，熊熊会将编号为 $n,n-1,...,n-x+1$ 的城市白魔法值加 $1$，这一操作会消耗熊熊 $x$ 点能量。

请问梦梦和熊熊一共需要至少消耗多少点能量，才能维护世界的和平。

输入格式

第一行一个正整数 $T$，表示数据组数。

之后对于每组数据，第一行一个正整数 $n$。

第二行给出 $n$ 个正整数，表示 $a_i$。

输出格式

对于每组数据，输出一行，表示答案。

样例输入1

4
5
1 1 1 1 1
10
0 0 0 0 1000000000 0 0 0 0 0
5
3 4 1 4 4
5
3 5 1 4 4

样例输出1

5
5000000000
16
18

样例解释1

对于第一组数据，梦梦执行一次参数 $5$。

对于第二组数据，梦梦执行 $1000000000$ 次参数 $5$​。

对于第三组数据，梦梦分别执行参数 $2,2,2$，熊熊分别执行参数 $4,2,2,2$。

对于第四组数据，梦梦分别执行参数 $2,2,2,2$，熊熊分别执行参数 $4,2,2,2$。

样例输入2

见下发文件。

样例输出2

见下发文件。

评测数据规模

对于 $20\%$ 的数据，$1 \leq a_i \leq 2$​​​​。

对于 $50\%$ 的数据，$1 \leq a_i \leq 10$。

对于 $100\%$ 的数据，$1 \leq T \leq 10,1 \leq n \leq 10^5,1 \leq a_i \leq 10^9$。