题目描述

给定一个长度为 n 的数组 a，可以选定一个区间 [l,r] 进行恰好一次操作，求操作后最大的 a_n - a₁。

操作方法：选定区间 [l,r] 和旋转次数 k，每次旋转为： a_l = a_l+1, a_l+1 = a_l+2, …, a_r-1 = a_r, a_r = a_l

输入格式

• 第一行一个整数 T (1 ≤ T ≤ 50)，表示测试样例组数。
• 对于每组测试样例：
  • 第一行为一个整数 n (1 ≤ n ≤ 2000)，表示数组长度。
  • 接下来一行为 n 个整数 a_i (1 ≤ a_i ≤ 999)，表示该数组。

数据保证 n ≤ 2000。

输出格式

对于每组测试样例输出一行一个整数，表示操作后最大的 a_n - a₁。

输入样例 #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, 9, 11, 5, 7]

操作后：
[1, 3, 5, 7, 9, 11]

则最终结果为：
11 - 1 = 10