#include <bits/stdc++.h>
#ifndef LOCAL
#include <xylophone.h>
#endif // LOCAL
using namespace std;
const int MAX = 5e3 + 5;
#ifdef LOCAL
int A[MAX];
int query(int s, int t){
return *max_element(A + s, A + t + 1) - *min_element(A + s, A + t + 1);
}
void answer(int i, int a){
// cout << i << " : " << a << '\n';
if(A[i] != a){
cout << "WRONG ANSWER\n";
exit(0);
}
}
#endif
int memo[MAX][MAX];
int ask(int l, int r){
assert(l <= r);
if(l == r) return 0;
if(memo[l][r] != 0) return memo[l][r];
return memo[l][r] = query(l, r);
}
void solve(int N){
memset(memo, 0, sizeof(memo));
if(N == 1){
answer(1, 1);
answer(2, 2);
return;
}
int l = 1, r = N, R = -1;
while(l <= r){
int mid = l + r >> 1;
if(ask(1, mid) == N - 1) R = mid, r = mid - 1;
else l = mid + 1;
}
l = 1, r = R - 1;
int L = 1;
while(l <= r){
int mid = l + r >> 1;
if(ask(mid, R) == N - 1) L = mid, l = mid + 1;
else r = mid - 1;
}
//find L, R that A[L] = 1, A[R] = N
vector<int> a(N + 1);
a[L] = 1;
a[R] = N;
if(L > 1) a[L - 1] = 1 + ask(L - 1, L);
if(R < N) a[R + 1] = N - ask(R, R + 1);
vector<bool> used(N + 1);
used[1] = used[N] = true;
auto casework = [&](int x, int y, int nextTwo, int nextThree){
int case1 = x - nextTwo;
if(max({case1, x, y}) - min({case1, x, y}) == nextThree) return case1;
int case2 = x + nextTwo;
if(max({case2, x, y}) - min({case2, x, y}) == nextThree) return case2;
cout << x << ' ' << y << ' ' << nextTwo << ' ' << nextThree << '\n';
assert(false);
};
for(int i = L - 2; i >= 1; --i){
int delta = ask(i, i + 1);
if(a[i + 1] - delta < 0 || used[a[i + 1] - delta]) a[i] = a[i + 1] + delta;
else if(a[i + 1] + delta > N || used[a[i + 1] + delta]) a[i] = a[i + 1] - delta;
else a[i] = casework(a[i + 1], a[i + 2], delta, ask(i, i + 2));
used[a[i]] = true;
}
for(int i = R + 2; i <= N; ++i){
int delta = ask(i - 1, i);
if(a[i - 1] - delta < 0 || used[a[i - 1] - delta]) a[i] = a[i - 1] + delta;
else if(a[i - 1] + delta > N || used[a[i - 1] + delta]) a[i] = a[i - 1] - delta;
else a[i] = casework(a[i - 1], a[i - 2], delta, ask(i - 2, i));
used[a[i]] = true;
}
if(L + 1 < R){
a[L + 1] = 1 + ask(L, L + 1);
for(int i = L + 2; i < R; ++i){
int delta = ask(i - 1, i);
if(a[i - 1] - delta < 0 || used[a[i - 1] - delta]) a[i] = a[i - 1] + delta;
else if(a[i - 1] + delta > N || used[a[i - 1] + delta]) a[i] = a[i - 1] - delta;
else a[i] = casework(a[i - 1], a[i - 2], delta, ask(i - 2, i));
used[a[i]] = true;
}
}
for(int i = 1; i <= N; ++i){
answer(i, a[i]);
}
}
#ifdef LOCAL
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int random(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
int main(){
srand(time(nullptr));
for(int itest = 1; itest <= 300; ++itest){
int N = random(2, 30);
iota(A + 1, A + 1 + N, 1);
shuffle(A + 1, A + 1 + N, rng);
// int N = 6;
// vector<int> vec = {1, 6, 5, 3, 2, 4};
// copy(vec.begin(), vec.end(), A + 1);
int pos1 = -1, posN = -1;
for(int i = 1; i <= N; ++i){
if(A[i] == 1) pos1 = i;
if(A[i] == N) posN = i;
}
if(pos1 > posN){
swap(pos1, posN);
swap(A[pos1], A[posN]);
}
cout << "The permutation length N : ";
for(int i = 1; i <= N; ++i) cout << A[i] << ' '; cout << '\n';
solve(N);
cout << "Passed\n";
}
return 0;
}
#endif // LOCAL
