#include <bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); i++)
#define R(i, j, k) for(int i = (j); i >= (k); i--)
#define ll long long
#define sz(a) ((int) a.size())
#define all(a) a.begin(), a.end()
#define vi vector<ll>
#define pb emplace_back
#define me(a, x) memset(a, x, sizeof(a))
#define fst first
#define snd second
#define ii pair<ll, ll>
using namespace std;
static int A[5000];
int query(int s,int t);
void answer(int i,int a);
void recl(int l,int r);
void recr(int l,int r);
bool flag=0;
int n;
void recr(int l,int r){
if(r==l)return;
int target=query(l,r);
int tl=l,tr=r;
while(r-l>1){
int m=(l+r)/2;
if(query(tl,m)==target){
r=m;
}else l=m;
}
if(flag)answer(r,A[tr]-target);
else answer(r,n);
recr(tl,r);recl(r,tr);
}
void recl(int l,int r){
if(r==l)return;
int target=query(l,r);
int tl=l,tr=r;
while(r-l>1){
int m=(l+r)/2;
if(query(m,tr)==target){
l=m;
}else r=m;
}
answer(l,A[tl]-target);
recr(tl,l);recl(l,tr);
}
void solve(int N) {
recr(1,N);
//~ L(i,0,N-1)cout<<A[i]<<" ";
//~ cout<<endl;
return;
}
