#include<stdio.h>
#include<algorithm>
#include<map>
typedef long long ll;
int n;
int a[100005];
std::map<ll,ll> val;
ll calc(const ll m)
{
    if(val.count(m))
    {
        return val[m];
    }
    ll f0(0),f1(__builtin_llabs(m-a[0]));
    for(int j=1;j<n;j++)
    {
        const ll f2(std::min(std::max(f0,__builtin_llabs(m-a[j-1]-a[j])),
                              std::max(f1,__builtin_llabs(m-a[j]))));
        f0=f1,f1=f2;
    }
    return val[m]=f1;
}
void solve()
{
    val.clear();
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",a+i),a[i]<<=1;
    }
    for(int i=20;i<=80;i++)
    {
        printf("%lld ",calc(i)-calc(i-1));
    }
    printf("\n");
    ll s(calc(-4000000000));
    for(ll p=-4000000000;p<4000000000;)
    {
        const ll v(calc(p)),d(calc(p+1)-calc(p));
        ll l(p),r(4000000000);
        while(l<=r)
        {
            const ll m(l+r>>1);
            if(calc(m)==v+d*(m-p))
            {
                l=m+1;
            }
            else
            {
                r=m-1;
            }
        }
        s=std::min(s,calc(r));
        p=r+calc(r)-s;
    }
    printf("%lld\n",s);
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        solve();
    }
    return 0;
}