CF1392C Omkar and Waterslide

Omkar 正在他的水上乐园建造一条滑水道，他需要你的帮助来确保建造过程尽可能高效。 Omkar 目前有 $n$ 个支架排成一行，第 $i$ 个支架的高度为 $a_i$。Omkar 想要从右向左建造滑水道，因此这些支架的高度必须是非递减的，才能支撑滑水道。在一次操作中，Omkar 可以选择任意一个高度非递减的连续子段，并将该子段内所有支架的高度都加 $1$。 请帮助 Omkar 计算，他最少需要进行多少次操作，才能使所有支架的高度满足从右到左非递减，从而能够支撑滑水道。 如果一个数组 $b$ 可以通过从数组 $c$ 的开头删除若干（可能为零或全部）元素和从结尾删除若干（可能为零或全部）元素得到，则称 $b$ 是 $c$ 的一个子段。 如果一个数组 $b_1, b_2, \dots, b_n$ 满足对每个 $i$（$1 \leq i < n$）都有 $b_i \leq b_{i+1}$，则称其为非递减数组。

每组测试数据包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 100$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \times 10^5$），表示 Omkar 拥有的支架数量。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$0 \leq a_i \leq 10^9$），表示每个支架的高度。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出一个整数，表示 Omkar 使支架能够支撑滑水道所需的最少操作次数。

Omkar 进行操作的子数组已加粗。 在第一个测试用例中： - 第一次操作： $[5, 3, \textbf{2}, 5] \to [5, 3, \textbf{3}, 5]$ - 第二次操作： $[5, \textbf{3}, \textbf{3}, 5] \to [5, \textbf{4}, \textbf{4}, 5]$ - 第三次操作： $[5, \textbf{4}, \textbf{4}, 5] \to [5, \textbf{5}, \textbf{5}, 5]$ 在第三个测试用例中，数组已经是非递减的，因此 Omkar 不需要进行任何操作。 由 ChatGPT 4.1 翻译