write a go solution for Description:
Mainak has an array a_1,a_2,ldots,a_n of n positive integers. He will do the following operation to this array exactly once:

- Pick a subsegment of this array and cyclically rotate it by any amount.

- Pick two integers l and r, such that 1<=l<=r<=n, and any positive integer k.
- Repeat this k times: set a_l=a_l+1,a_l+1=a_l+2,ldots,a_r-1=a_r,a_r=a_l (all changes happen at the same time).

Mainak wants to maximize the value of (a_n-a_1) after exactly one such operation. Determine the maximum value of (a_n-a_1) that he can obtain.

Input Format:
Each test contains multiple test cases. The first line contains a single integer t (1<=t<=50) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer n (1<=n<=2000).

The second line of each test case contains n integers a_1,a_2,ldots,a_n (1<=a_i<=999).

It is guaranteed that the sum of n over all test cases does not exceed 2000.

Output Format:
For each test case, output a single integer — the maximum value of (a_n-a_1) that Mainak can obtain by doing the operation exactly once.

Note:
- In the first test case, we can rotate the subarray from index 3 to index 6 by an amount of 2 (i.e. choose l=3, r=6 and k=2) to get the optimal array: [1, 3, \underline{9, 11, 5, 7}] \longrightarrow [1, 3, \underline{5, 7, 9, 11}] So the answer is a_n-a_1=11-1=10.
- In the second testcase, it is optimal to rotate the subarray starting and ending at index 1 and rotating it by an amount of 2.
- In the fourth testcase, it is optimal to rotate the subarray starting from index 1 to index 4 and rotating it by an amount of 3. So the answer is 8-1=7.. Output only the code with no comments, explanation, or additional text.