P1020日月风随（solwind）

【题目背景】

修复系统后，tfbz 得知萨米旧都长期压迫并封锁星尘镇，于是决定与朋友们反抗暴政。为了联络外援，他必须解除山谷中的封锁，让隐藏的古道重新显现。

【题目描述】

山谷中依次排列着 $n$ 座风候台，从西向东编号为 $1\sim n$。第 $i$ 座风候台上系着一枚镇风结，这枚结最初的韧度为 $h_i$。

tfbz 走入山谷时，所有镇风结都牢牢束在风候台上，山谷中没有一丝风。只有将它们全部解开，风才能贯穿整条山谷，隐藏的古道也才会重新显现。

最直接的办法是逐一削弱这些镇风结。举行仪式前，tfbz 可以消耗行旅灵力削弱任意一枚尚未解开的镇风结。每消耗 $1$ 点行旅灵力，这枚结的当前韧度减少 $1$；当韧度降至 $0$ 时，它会被直接解开。

但若只依靠这种方法，tfbz 可能需要消耗大量灵力。风候台上留下的文字告诉他，在完成提前削弱后，他必须恰好举行一次名为“日月风随”的引风仪式。他需要选择一座仍系着镇风结的风候台，并投入一个正整数 $x$ 点行旅灵力，让强度为 $x$ 的风势首先冲击这枚结。

若一枚当前韧度为 $h$ 的镇风结受到强度为 $y$ 的风势：

• 当 $h>y$ 时，它的韧度减少 $y$，风势不再从这个方向继续传播；
• 当 $h\leq y$ 时，它会被解开，并向编号相差 $1$、且镇风结仍未解开的风候台传递强度为 $h-1$ 的风势。

若某个方向上不存在相邻的风候台，或相邻风候台上的镇风结已经解开，风势便不能向这个方向传播。已经解开镇风结的风候台不会消失，它两侧的风候台也不会因此变得相邻。

一枚镇风结被解开时，产生的风势会分别尝试向左右两侧传播；两个方向上的传播互不替代。整个过程会持续到没有新的镇风结被解开为止。

这次行动的总消耗，等于仪式前使用的行旅灵力与举行引风仪式时投入的 $x$ 之和。tfbz 必须让所有镇风结在仪式结束时都已解开，才能带着同伴穿过重新显现的古道。他想知道，完成这一切至少需要消耗多少点行旅灵力。

【输入格式】

从文件 $\textbf{\textit{solwind.in}}$ 中读入数据。

本题有多组测试数据。第一行一个正整数 $T$，表示测试数据组数。

对于每组测试数据，第一行一个正整数 $n$，表示风候台的数量。

第二行 $n$ 个正整数 $h_1,h_2,\ldots,h_n$，其中 $h_i$ 表示第 $i$ 座风候台上镇风结的初始韧度。

【输出格式】

输出到文件 $\textbf{\textit{solwind.out}}$ 中。

对于每组测试数据，输出一个整数，表示 tfbz 最少需要消耗的行旅灵力。

【样例 1 输入】

142332 1 24451 2 3 261778592 4 3 2 1

【样例 1 输出】

14233744

【说明/提示】

【样例 1 解释】

对于第一组测试数据，tfbz 可以先消耗 $2$ 点行旅灵力，直接解开第 $3$ 座风候台上的镇风结；随后选择第 $1$ 座风候台，投入 $x=2$ 点行旅灵力举行引风仪式。第 $1$ 枚镇风结解开后产生强度为 $1$ 的风势，并继续解开第 $2$ 枚镇风结，总消耗为 $4$。

对于第二组测试数据，tfbz 无需提前削弱任何镇风结。选择第 $3$ 座风候台并投入 $x=3$ 点行旅灵力后，风势可以向两侧传播并解开所有镇风结，因此答案为 $3$。

【样例 2】

见选手目录下的 $\textbf{\textit{solwind/solwind2.in}}$ 和 $\textbf{\textit{solwind/solwind2.ans}}$。

该组样例符合测试点 $1\sim 6$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{solwind/solwind3.in}}$ 和 $\textbf{\textit{solwind/solwind3.ans}}$。

该组样例符合测试点 $7\sim 12$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{solwind/solwind4.in}}$ 和 $\textbf{\textit{solwind/solwind4.ans}}$。

该组样例符合测试点 $13\sim 19$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{solwind/solwind5.in}}$ 和 $\textbf{\textit{solwind/solwind5.ans}}$。

该组样例符合测试点 $20\sim 25$ 的数据范围。

【数据范围】

对于 $100\%$ 的数据，保证：$1\leq T\leq 10^4$，$1\leq n\leq 3\times 10^5$，$1\leq h_i\leq 10^6$，且单个测试点内所有测试数据的 $n$ 之和不超过 $3\times 10^5$。

特殊性质：对于每组测试数据，均满足 $h_1=h_2=\cdots=h_n$。