给定一个包含 $n$ 个整数的数组 $a$。你可以执行至多一次以下操作：

• 选择任意整数 $1 \le l \le r \le n$ 和任意整数 $x$。然后，对于每个 $l \le i \le r$，将 $a_i$ 替换为 $a_i + x$。

求执行至多一次该操作后，$\max(a_1, a_2, \dots, a_n) - \min(a_1, a_2, \dots, a_n)$ 的最小值。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^5$)，表示测试用例的数量。接下来是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 2 \cdot 10^5$)，表示数组的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$)，表示数组元素。

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

输出格式

对于每个测试用例，输出一行，包含一个整数，表示执行至多一次操作后，$\max(a_1, a_2, \dots, a_n) - \min(a_1, a_2, \dots, a_n)$ 的最小值。

样例

样例输入 1

4
3
42 42 42
4
1 2 2 1
5
1 100 1 100 1
6
1 2 3 4 5 6

样例输出 1

0
0
99
2

说明

在第一个测试用例中，不需要进行任何操作，因为 $\max - \min$ 已经为 $0$。

在第二个测试用例中，可以选择 $x = -1$ 和区间 $a[2 : 3]$。数组将变为 $[1, 1, 1, 1]$，此时 $\max - \min = 0$。

在第三个测试用例中，初始的 $\max - \min$ 为 $99$。遗憾的是，无法通过单次操作减小该值。

在第四个测试用例中，初始的 $\max - \min$ 为 $5$，但我们可以选择 $x = 3$ 和区间 $a[1 : 3]$。数组将变为 $[4, 5, 6, 4, 5, 6]$，此时 $\max - \min = 2$。