#include<stdio.h>
#include<algorithm>
#include<map>
#define INF 4000000000
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=-50;i<=0;i++)
    {
        printf("%lld ",calc(i));
    }
    printf("\n");
    ll s(calc(-INF)),p(-INF);
    for(int t=0;p<INF&&t<30;t++)
    {
        const ll v(calc(p)),d(calc(p+1)-calc(p));
        ll l(p),r(INF);
        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;
    }
    ll q(INF);
    for(int t=0;q>p&&t<30;t++)
    {
        const ll v(calc(q)),d(calc(q-1)-calc(q));
        ll l(-INF),r(q);
        while(l<=r)
        {
            const ll m(l+r>>1);
            if(calc(m)==v+d*(q-m))
            {
                r=m-1;
            }
            else
            {
                l=m+1;
            }
        }
        s=std::min(s,calc(l));
        q=l-calc(l)+s;
    }
    printf("%lld\n",s);
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        solve();
    }
    return 0;
}