题目描述

一条走廊上依次排着 $n$ 个打卡点，编号为 $1$ 到 $n$。一开始，每个打卡点的计数都为 $0$。

有一个巡检机器人进行若干回合的打卡操作。

• 第 $1$ 回合：机器人必须被放到 $1$ 号打卡点。
• 除第 $1$ 回合外的每一回合：机器人必须执行下面两种操作中的恰好一种：
  1. 如果当前位于 $i$ 号点且 $i<n$，可以移动到 $i+1$ 号点；
  2. 可以传送到任意一个打卡点（也允许传送到当前位置）。

每一回合结束时，机器人所在打卡点的计数都会增加 $1$。

现在给出目标计数序列 $a_1,a_2,\dots,a_n$。请你求出：为了最终恰好得到该序列，机器人最少需要传送多少次。

输入格式

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

接下来对于每组测试数据：

• 第一行一个整数 $n$；
• 第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。

数据规模：

• $1 \le t \le 10^4$
• $1 \le n \le 2 \times 10^5$
• $0 \le a_i \le 10^9$
• $a_1 \ge 1$
• 所有测试数据中，$n$ 的总和不超过 $2 \times 10^5$

可以证明，在上述约束下一定存在可行方案。

输出格式

对于每组测试数据，输出一个整数，表示最少传送次数。

4
4
1 2 2 1
5
1 0 1 0 1
5
5 4 3 2 1
1
12

1
2
4
11

Hint

样例解释： 以第一组数据 $1,2,2,1$ 为例，一种最优方案如下：

1. 第 $1$ 回合将机器人放到 $1$ 号点，计数变成 $[1,0,0,0]$；
2. 向右移动到 $2$ 号点，计数变成 $[1,1,0,0]$；
3. 向右移动到 $3$ 号点，计数变成 $[1,1,1,0]$；
4. 传送到 $2$ 号点，计数变成 $[1,2,1,0]$；
5. 向右移动到 $3$ 号点，计数变成 $[1,2,2,0]$；
6. 向右移动到 $4$ 号点，计数变成 $[1,2,2,1]$。

共传送 $1$ 次。