Problem Description
A sequence can be decomposed into the sum of unit impulses, but we can still decompose the sequence into the sum of gate function which defined as
.
For simplify we use G (a,b) to represent , Now the question is how to decompose the sequence to maximize the minimum length of gate function. (The length of is b – a + 1). For simplification, you just need to get the minimum length.
Input
The first integer T is the number of test cases
Each case starts with a number N followed by N integers ai
(0<= N <= 10000)
(0 <= a[i] <= 2^31)
(We ensure )
Output
The minimum length S
Sample Input
2
6
2 3 4 3 3 1
5
2 2 2 2 2
Sample Output
3
5