E. 陷阱魔法 I
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

猪猪学院的魔法师小猪正在研究一种有趣的陷阱魔法。

这个陷阱魔法会困住 $$$n$$$ 只小猪，并让它们排成一排。这 $$$n$$$ 只小猪分别编号为 $$$1$$$ 到 $$$n$$$。

初始时，编号为 $$$i$$$ 的小猪的「不能动数」为 $$$a_i$$$，并且 $$$a_1,a_2,\ldots,a_n$$$ 恰好构成一个长度为 $$$n$$$ 的排列$$$^{\text{∗}}$$$。

初始时，魔法师小猪需要向陷阱中注入魔力，注入的魔力值是一个非负整数 $$$x$$$：

随后，魔法师小猪可以进行任意多次以下操作：

  • 选择一个区间 $$$[l,r]$$$（$$$1\le l\le r\le n$$$），需要满足当前区间内的小猪的「不能动数」的最大值和最小值的差不超过 $$$x$$$，即： $$$$$$ \max \limits_{l \leq i \leq r} a_i - \min \limits_{l \leq i \leq r} a_i \leq x $$$$$$
  • 随后，将这个区间内的小猪的「不能动数」任意重排。也就是说，可以任意改变这个区间内小猪的「不能动数」的相对顺序。

如果从左到右看，小猪们的「不能动数」严格递增，那么陷阱就会被破解。

为了深入研究这个陷阱魔法的效果，小猪们想知道：对于给定的场面，至少需要注入多少点魔力，才能破解陷阱？

$$$^{\text{∗}}$$$如果一个长度为 $$$k$$$ 的整数序列 $$$[c_1, c_2, \ldots, c_k]$$$ 满足：$$$1$$$ 到 $$$k$$$ 中的每个整数（包括 $$$1$$$ 和 $$$k$$$）都恰好在序列中出现一次，那么我们称序列 $$$c$$$ 是一个长度为 $$$k$$$ 的排列。例如 $$$[1, 2, 3]$$$、$$$[1, 5, 3, 2, 4]$$$ 都是排列，而 $$$[1, 1, 4]$$$ 不是。

Input

本题的输入包含多组测试用例。

第一行一个整数 $$$T$$$（$$$1 \leq T \leq 10^5$$$），表示测试用例的数量。对于每组测试用例：

  • 第一行一个整数 $$$n$$$（$$$1\le n\le 10^5$$$），表示小猪的数量。
  • 第二行 $$$n$$$ 个整数 $$$a_1,a_2,\ldots,a_n$$$（$$$1 \leq a_i \leq n$$$），表示初始时刻每只小猪的「不能动数」。
  • 数据保证 $$$[a_1, a_2, \ldots, a_n]$$$ 构成一个排列。

保证所有测试用例的 $$$n$$$ 的总和不超过 $$$10^5$$$。

Output

对于每组测试用例：

  • 输出一行一个整数，表示破解陷阱所需的最小魔力值 $$$x$$$。
Example
Input
2
5
1 2 3 4 5
6
2 5 1 6 3 4
Output
0
4
Note

对于第一组测试用例，初始队列为 $$$[1,2,3,4,5]$$$。因为小猪们的「不能动数」已经严格递增，因此不需要操作。注入 $$$x = 0$$$ 的魔力即可。

对于第二组测试用例，初始队列为 $$$[2,5,1,6,3,4]$$$，注入 $$$x = 4$$$ 的魔力，并依次进行操作：

  • $$$[\underline{\color{blue}{2,5,1}},6,3,4] \to [\underline{\color{blue}{1,2,5}},6,3,4]$$$；
  • $$$[1,2,\underline{\color{blue}{5,6,3,4}}] \to [1,2,\underline{\color{blue}{3,4,5,6}}]$$$；

可以证明，当 $$$x \lt 4$$$ 时无法破解陷阱，所以第二组测试用例的答案为 $$$4$$$。