#pragma GCC optimize("Ofast")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include "xylophone.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define e1 first
#define e2 second
#define uint uint_fast64_t
#define ll int_fast64_t
#define ull uint_fast64_t
#define int16 int_fast16_t
#define uint16 uint_fast16_t
#define int32 int_fast32_t
#define uint32 uint_fast32_t
#define int64 int_fast64_t
#define uint64 uint_fast64_t
#define ld long double
#define float long double
#define size(x) (int)x.size()
#define satori int testCases; cin>>testCases; while(testCases--)
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define all(r) begin(r),end(r)
#define rall(r) rbegin(r),rend(r)
#define time chrono::high_resolution_clock().now().time_since_epoch().count()
#define elapsed(__begin,__end) (__end-__begin)/CLOCKS_PER_SEC
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
float pi=3.14159265358979323846;
const int MAXN=5e3+10,inf=1e9+2137;
/*
int a[MAXN],b[MAXN];
int query(int l,int r)
{
int mn=inf,mx=-inf;
for(int i=l;i<=r;i++)
mn=min(mn,a[i]),mx=max(mx,a[i]);
return mx-mn;
}
int answer(int i,int v)
{
b[i]=v;
}
*/
int h[MAXN],d[MAXN],t[MAXN];
void solve(int n)
{
for(int i=1;i<n;i++)
d[i]=query(i,i+1);
for(int i=1;i<n-1;i++)
t[i]=query(i,i+2);
h[2]=d[1];
for(int i=3;i<=n;i++)
{
if(d[i-2]>d[i-1])
{
if(h[i-2]>h[i-1])
{
if(t[i-2]>d[i-2])
h[i]=h[i-1]-d[i-1];
else
h[i]=h[i-1]+d[i-1];
}
else
{
if(t[i-2]>d[i-2])
h[i]=h[i-1]+d[i-1];
else
h[i]=h[i-1]-d[i-1];
}
}
else
{
if(h[i-2]>h[i-1])
{
if(t[i-2]==d[i-2]+d[i-1])
h[i]=h[i-1]-d[i-1];
else
h[i]=h[i-1]+d[i-1];
}
else
{
if(t[i-2]==d[i-2]+d[i-1])
h[i]=h[i-1]+d[i-1];
else
h[i]=h[i-1]-d[i-1];
}
}
}
int lp=1,rp=1;
for(int i=2;i<=n;i++)
lp=(h[i]<h[lp]?i:lp),rp=(h[i]>h[rp]?i:rp);
if(rp<lp)
for(int i=1;i<=n;i++)
h[i]*=-1;
int mn=0;
for(int i=2;i<=n;i++)
mn=min(mn,h[i]);
for(int i=1;i<=n;i++)
h[i]+=-mn+1;
for(int i=1;i<=n;i++)
answer(i,h[i]);
}
/*
int main()
{
a[1]=2,a[2]=1,a[3]=5,a[4]=3,a[5]=4;
solve(5);
for(int i=1;i<=5;i++)
cout<<b[i]<<' ';
}
*/
