爆炸

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

一排 $n$ 个怪物的初始生命值为 $h_1,h_2,\ldots,h_n$。普通攻击消耗 $1$ 点能量并造成 $1$ 点伤害，可以使用任意次。最后必须恰好使用一次爆炸攻击结束游戏。

爆炸攻击选择能量 $x$ 和一个目标怪物。若目标当前生命值不超过 $x$，它死亡并向仍存活的相邻怪物造成“死亡前生命值减一”的伤害；被这次伤害击杀的怪物会按相同规则继续向两侧引发爆炸。普通攻击也可提前杀死怪物，但怪物不会移动，已死亡位置不会让两侧怪物变为相邻。

求普通攻击次数与最后一次爆炸能量之和的最小值。

输入格式

第一行一个整数 $t$，表示测试数据组数。

每组数据第一行一个整数 $n$，第二行包含 $n$ 个正整数 $h_1,h_2,\ldots,h_n$。

输出格式

对每组数据输出一行一个整数，表示最小总能量。

样例输入

5
3
1 1 1
4
4 1 2 1
4
5 10 15 10
1
42
9
1 2 3 2 2 2 3 2 1

样例输出

3
6
15
42
12

数据范围

$1\le t\le10^4$，$1\le n\le3\times10^5$，$1\le h_i\le10^6$，所有测试数据的 $n$ 之和不超过 $3\times10^5$。