#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; }