题目内容

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

输入描述

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

解题思路与方法

问题建模

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

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

即