#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<<i<<" "<<a<<endl;
if(cevler[i]!=a)cout<<"a "<<i<<" "<<cevler[i]<<" "<<a<<endl;
int of;
}*/
int bir_bul(int N){
int hed=query(1,N);
int l=2,r=N;
int left=2;
while(l<=r){
int mid=(l+r)/2;
int a=query(1,mid);
if(a!=hed)l=mid+1;
else{
left=mid;
r=mid-1;
}
}
//cout<<left<<endl;
int ans=-1;
l=1,r=left-1;
while(l<=r){
int mid=(l+r)/2;
int a=query(mid,left);
//cout<<l<<" "<<r<<" "<<mid<<" "<<a<<endl;
if(a!=hed)r=mid-1;
else{
ans=mid;
l=mid+1;
}
//cout<<ans<<endl;
}
return ans;
}
void solve(int N){
int mn=bir_bul(N);
//cout<<mn<<endl;
//return;
set<int> st;
st.ins(1);
answer(mn,1);
int a=1,b;
if(mn!=N){
b=1+query(mn,mn+1);
st.ins(b);
answer(mn+1,b);
}
for(int i=mn+2;i<=N;i++){
int ok=0,x=query(i-1,i);
int ans=0;
if(b+x>N||st.find(b+x)!=st.end())ans=b-x;
if(b-x<1||st.find(b-x)!=st.end())ans=b+x;
if(ans==0){
ok=query(i-2,i);
if(a<b){
if(ok==b+x-a)ans=b+x;
else ans=b-x;
}
else{
if(ok==a-b+x)ans=b-x;
else ans=b+x;
}
}
st.ins(ans);
answer(i,ans);
a=b;
b=ans;
}
a=1;
if(mn!=1){
b=1+query(mn-1,mn);
st.ins(b);
answer(mn-1,b);
}
for(int i=mn-2;i>0;i--){
int ok=0,x=query(i,i+1);
int ans=0;
if(b+x>N||st.find(b+x)!=st.end())ans=b-x;
if(b-x<1||st.find(b-x)!=st.end())ans=b+x;
if(ans==0){
ok=query(i,i+2);
if(a<b){
if(ok==b+x-a)ans=b+x;
else ans=b-x;
}
else{
if(ok==a-b+x)ans=b-x;
else ans=b+x;
}
}
st.ins(ans);
answer(i,ans);
a=b;
b=ans;
}
}
/*
signed main(){
//lalala;
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>cevler[i];
solve(n);
}*/
