Omkar 正在他的水上公园建造滑水道,他需要你的帮助以确保他尽可能高效地完成这项工作。
Omkar 目前有 $$$n$$$ 个支撑排列成一条线,其中第 $$$i$$$ 的高度为 $$$a_i$$$。 Omkar 想要从右到左建造他的滑水道,因此他的支架高度必须不降低才能支撑滑水道。在 $$$1$$$ 操作中,Omkar 可以执行以下操作:获取高度不减少的支撑的任何连续子段,并将 $$$1$$$ 添加到每个高度。
帮助 Omkar 找到他需要执行的最少操作次数,才能让他的支撑物能够支撑他的滑水道!
数组 $$$b$$$ 是数组 $$$c$$$ 的子段,如果 $$$b$$$ 可以通过删除开头的几个(可能是零个或全部)元素和结尾的几个(可能是零个或全部)元素从 $$$c$$$ 获得。
如果 $$$b_i\le b_{i+1}$$$ 对于从 $$$1$$$ 到 $$$n-1$$$ 的每个 $$$i$$$,则数组 $$$b_1, b_2, \dots, b_n$$$ 被称为非减数组。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \leq t \leq 100$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — Omkar 的支持数量。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_{1},a_{2},...,a_{n}$$$ $$$(0 \leq a_{i} \leq 10^9)$$$ - 支撑的高度。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - Omkar 需要执行的最小操作数才能使他的支撑物能够支撑他的滑水道。
示例
输入 #1
3 4 5 3 2 5 5 1 2 3 5 3 3 1 1 1
输出 #1
3 2 0
注意
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 执行 $$$0$$$ 操作。