#include <bits/stdc++.h>
using namespace std;
//#define lalala ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
//#define endl '\n'
//#define int long long int
#define ll long long
#define NN 5005
#define carp 10000000
#define pb push_back
#define p push
#define ins insert
#define f first
#define s second
int query(int s,int t);
void answer(int i,int a);
int cevler[NN];
/*int query(int s,int t){
//cout<<s<<" "<<t<<endl;
int mn=NN,mx=-1;
for(int i=s;i<=t;i++){
mn=min(mn,cevler[i]);
mx=max(mx,cevler[i]);
}
//int a;cin>>a;
return mx-mn;
}
void answer(int i,int a){
//cout<<a<<endl;
if(cevler[i]!=a)cout<<"a "<<i<<" "<<cevler[i]<<" "<<a<<endl;
int of;
}*/
vector<int> arr[NN],seg[NN*4];
int deg[NN*4];
int val[NN];
void yap(int x,int fark,int kim){
vector<int> a[2],b[2];
a[0]=seg[x*2],b[0]=seg[x*2+1];
if(12){
int mx=0;
for(auto u:a[0]){
mx=max(mx,u);
}
for(auto u:a[0])a[1].pb(mx-u);
mx=0;
for(auto u:b[0]){
mx=max(mx,u);
}
for(auto u:b[0])b[1].pb(mx-u);
}
int ind=0;
int yes=0;
for(int i=0;i<2&&kim!=1;i++){
for(int j=0;j<2;j++){
if(seg[x].size())break;
set<int> st;
int mx=0,son=0;
for(auto u:a[i]){
mx=max(mx,u);
son=u;
st.ins(u);
}
int ok=1,okey=1;
for(auto u:b[j]){
if(ok){
son-=u;
ok=0;continue;
}
mx=max(mx,u+son);
if(st.find(u+son)!=st.end()||u+son<0){okey=0;break;}
//st.ins(u+son);
}
if(mx!=fark)okey=0;
if(okey){
for(auto u:a[i])seg[x].pb(u);
ok=1;
for(auto u:b[j]){
if(ok){
ok=0;continue;
}
seg[x].pb(u+son);
}
}
}
}
for(int i=0;i<2&&kim!=2;i++){
for(int j=0;j<2;j++){
if(seg[x].size())break;
set<int> st;
int mx=0,son=-1;
for(auto u:b[j]){
mx=max(mx,u);
if(son==-1)son=u;
st.ins(u);
}
int ok=0,okey=1;
//reverse(a[i].begin(),a[i].end());
//if(a[i].size())
if(a[i].size())son-=a[i][a[i].size()-1];
for(auto u:a[i]){
ok++;
if(ok==a[i].size())break;
mx=max(mx,u+son);
if(st.find(u+son)!=st.end()||u+son<0){okey=0;break;}
//st.ins(u+son);
}
if(mx!=fark)okey=0;
if(okey){
for(auto u:a[i])seg[x].pb(u+son);
ok=1;
for(auto u:b[j]){
if(ok){
ok=0;continue;
}
seg[x].pb(u);
}
}
}
}
}
void bui(int x,int l,int r){
if(l>r)return;
if(l==r){
seg[x]=arr[l];
deg[x]=val[l];return;
}
int mid=(l+r)/2;
bui(x*2,l,mid);bui(x*2+1,mid+1,r);
deg[x]=query(l,r+1);
if(deg[x]==deg[x*2])yap(x,deg[x],2);
else if(deg[x]==deg[x*2+1])yap(x,deg[x],1);
else yap(x,deg[x],0);
/*cout<<x<<" "<<l<<" "<<r+1<<": "<<deg[x]<<endl;
for(int i=l;i<=r+1;i++){
cout<<cevler[i]<<" ";
}cout<<endl;
for(auto u:seg[x])cout<<u<<" ";
cout<<endl<<endl;*/
}
void solve(int N){
for(int i=1;i<N;i++){
int de=query(i,i+1);
arr[i]={0,de};
val[i]=de;
}
bui(1,1,N-1);
int ok=1;
for(auto u:seg[1]){
if(u==0)break;
if(u==N-1){ok=0;break;}
}
if(ok==0){
for(int i=0;i<seg[1].size();i++){
seg[1][i]=N-1-seg[1][i];
}
}
for(int i=0;i<seg[1].size();i++){
answer(i+1,seg[1][i]+1);
}
}
/*
signed main(){
//lalala;
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>cevler[i];
solve(n);
}*/
