Mainak 有一个包含 $$$n$$$ 正整数的数组 $$$a_1, a_2, \ldots, a_n$$$。他将对这个数组执行一次以下操作:
- 选择该数组的一个子段并将其循环旋转任意数量。
- 选择两个整数 $$$l$$$ 和 $$$r$$$,使得 $$$1 \le l \le r \le n$$$,以及任何正整数 $$$k$$$。
- 重复此 $$$k$$$ 次:设置 $$$a_l=a_{l+1}, a_{l+1}=a_{l+2}, \ldots, a_{r-1}=a_r, a_r=a_l$$$ (所有更改同时发生)。
Mainak 希望在一次这样的操作之后最大化 $$$(a_n - a_1)$$$ 的值。确定他可以获得的$$$(a_n - a_1)$$$的最大值。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 50$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2000$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 999$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2000$$$。
输出
对于每个测试用例,输出一个整数——Mainak 通过执行一次操作可以获得的 $$$(a_n - a_1)$$$ 的最大值。
示例
输入 #1
5 6 1 3 9 11 5 7 1 20 3 9 99 999 4 2 1 8 1 3 2 1 5
输出 #1
10 0 990 7 4
注意
- 在第一个测试用例中,我们可以将子数组从索引 $$$3$$$ 旋转到索引 $$$6$$$ $$$2$$$(即选择 $$$l = 3$$$、$$$r = 6$$$ 和 $$$k = 2$$$)以获得最佳数组:$$$$$$[1, 3, \underline{9, 11, 5, 7}] \longrightarrow [1, 3, \underline{5, 7, 9, 11}]$$$$$$ 所以答案是 $$$a_n - a_1 = 11 - 1 = 10$$$。
- 在第二个测试用例中,最佳旋转从索引 $$$1$$$ 开始和结束的子数组,并将其旋转 $$$2$$$ 的量。
- 在第四个测试用例中,最佳旋转从索引 $$$1$$$ 开始的子数组到索引 $$$4$$$ 并旋转 $$$3$$$ 的量。所以答案是 $$$8 - 1 = 7$$$。