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.
The first integer T is the number of test cases
Each case starts with a number N followed by N integers a[i]
(0<= T <= 10)
(0<= N <= 10000)
(0 <= a[i] <= 2^31)
(We ensure )