time limit per test

1 second

memory limit per test

256 megabytes

Mainak has an array a1,a2,…,an 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.

Formally, he can do the following exactly once:

• Pick two integers l and r, such that 1≤l≤r≤n, and any positive integer k.
• Repeat this k times: set al=al+1,al+1=al+2,…,ar−1=ar,ar=al (all changes happen at the same time).

Mainak wants to maximize the value of (an−a1) after exactly one such operation. Determine the maximum value of (an−a1) that he can obtain.

Input

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 a1,a2,…,an (1≤ai≤999).

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

Output

For each test case, output a single integer — the maximum value of (an−a1) that Mainak can obtain by doing the operation exactly once.

Example

Input

Copy

5

6

1 3 9 11 5 7

1

20

3

9 99 999

4

2 1 8 1

3

2 1 5

Output

Copy

10
0
990
7
4

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,9,11,5,7–––––––––]⟶[1,3,5,7,9,11–––––––––]

  So the answer is an−a1=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.

解题说明：此题采用贪心算法，首先找出数列中最大值和最小值，然后分别考虑下面三种情况，把最小的放第一位、把最大的放最后以及找出a[ i ]  - a[ i + 1 ] 的最大值，在这三种情况下求出最大值。

#include<stdio.h>
int main()
{
	int n, m, a, b, min, max, i, j, max1;
	int arr[2005] = { 0 };
	scanf("%d", &n);
	for (j = 1; j <= n; j++)
	{
		scanf("%d", &m);
		for (i = 1; i <= m; i++)
		{
			scanf("%d", &arr[i]);
		}
		min = arr[1];
		max = arr[1];
		a = 0;
		b = 0;
		for (i = 1; i <= m; i++)
		{
			if (arr[i] <= min)
			{
				min = arr[i];
			}
			if (arr[i] >= max)
			{
				max = arr[i];
			}
		}
		max1 = max - arr[1] > arr[m] - min ? max - arr[1] : arr[m] - min;
		for (i = 1; i < m; i++)
		{
			if (max1 < arr[i] - arr[i + 1])
			{
				max1 = arr[i] - arr[i + 1];
			}
		}
		printf("%d\n", max1);
	}
	return 0;
}