题目描述

存在 $n$ 个数，每次操作可以任选一个区间使得区间内的所有数字减一。问最少多少次操作，可以让所有数都变成 $1$。

数据保证一定有解。

输入格式

输入 $t$，代表有 $t$ 组数据。每组数据输入 $n$，代表有 $n$ 个数。接下来一行输入 $n$ 个数。

输出格式

每组数据输出一个整数，代表最少需要操作的次数。

输入数据 1

1
6
1 3 5 2 7 1

输出数据 1

9

输入数据 2

2
1
1
4
2 2 2 2

输出数据 2

0
1

输入数据 3

1
5
5 4 3 2 1

输出数据 3

4

数据范围与约定

$t\le1000$，$n<10^5$，所有测试中 $\sum n<10^6$，每个数字小于 $10^6$。