解题思路与方法

问题建模

我们需要对一个长度为 $n$ 的高度序列 $h_1, h_2, \dots, h_n$ 进行最少次数的“调整”，使得调整后的高度序列严格单调递增且相邻差至少为 1（高度为整数）。每次调整可将某个位置的高度改为任意整数；未调整的位置保持原值。

若我们选择不调整的一组位置 $S=i_1<i_2<\cdots<i_k$，并将其它位置在这两个未调整点之间“插值”成整数严格递增序列，那么必须保证对于任意相邻的 $i_j,i_{j+1}\in S$，都有

即

题目内容

多多想要举办一场助农音乐节，音乐节将在收获果实的风景优美的山区举行，以提供独特的视听体验。然而，山区的自然地形往往起伏不平。为了确保观众的安全和良好的视听效果，场地的地形高度需要进行合理调整，确保每个位置的高度都要高于前一个位置，从而避免因地形起伏造成的摔倒或视线遮挡。在实际地形中，可能存在一些低洼区域需要填充，以及一些过高的区域需要切削。为了解决这一问题，多多希望通过尽量少的地形调整(即调整最少的测量点高度)，使整个场地的高度呈现严格上升的形态。请你帮多多计算，为了确保音乐节的成功举办，最少需要对多少个位置进行地形调整注意：数据范围仅限制输入值，调整后的数值可以超出范围。如调整后的高度可以为负数(允许变为谷底)

输入描述

第一行为一个整数 $T(1\leq T\leq 10)$, 表示共有 $T$ 个测试数据。

每组测试数据：

第一行为一个整数 $n(1\leq n\leq 100000)$，表示山区的测量点高度总数。

第二行有 $n$ 个整数 $h_i(1\leq h_i\leq 100000)$,表示每个测量点 $i$ 的地形高度。

输出描述

每组数据输出一个结果，每个结果占一行

补充说明

对于 $20$% 的数据有：$1\leq n\leq 1000$

对于 $100$% 的数据有：$1\leq n\leq 100000$

数据范围仅限制输入值，调整后的数值可以超出范围。如调整后的高度可以为负数(允许变为谷底)

示例1

输入

1
4
5 3 6 2

输出

2

说明

最少的地形调整次数为 $2$，可将下标为 $0$ 的 $5$ 调整为 $2$，下标为 $3$ 的 $2$ 调整为 $7$。

示例2

输入

1
3
1 2 3

输出

0

说明

最少的地形调整次数为 $0$，初始的高度已经满足要求。