#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl
void solve(int N);
int query(int s, int t);
void answer(int i, int a);
using ll = long long;
const ll mod = 1e9+7;
const int maxn = 1e6 + 5;
int A[maxn];
int n;
bool used[maxn];
int A1[maxn];
int A2[maxn];
void Set(int i, int a) {
answer(i,a);
used[a]=true;
A[i]=a;
}
void ask1(int i) {
if (A1[i]) return;
A1[i] = query(i,i+1);
}
void ask2(int i) {
assert(i+2<=n);
if (A2[i]) return;
A2[i] = query(i,i+2);
}
bool isUsed(int x) {
if (x<1 || x>n) return true;
return used[x];
}
void solve(int _n) {
n=_n;
int in = -1;
// find in
{
int lo = 1;
int hi = n;
while (hi-lo>1) {
int mid = (lo+hi)/2;
if (query(1,mid)==n-1) {
hi = mid;
} else {
lo = mid;
}
}
in = hi;
}
auto bruteL = [&](int i) {
//watch(i);
assert(i+2<=n);
assert(A[i+1]); assert(A[i+2]);
ask1(i);
ask1(i+1);
ask2(i);
vector<int> op;
op.push_back(A[i+1]-A1[i]);
op.push_back(A[i+1]+A1[i]);
for (int x: op) {
if (x<1 || x>n) continue;
A[i]=x;
bool ok = true;
int gap=max(abs(A[i]-A[i+1]),abs(A[i+1]-A[i+2]));
if (gap > A2[i]) {
ok = false;
}
if (A1[i] < A2[i] && A1[i+1]==A2[i]) {
// we have to be in the middle
// 2 3 1 or 2 1 3
int lo = min(A[i+1],A[i+2]);
int hi = max(A[i+1],A[i+2]);
if (!(lo<A[i] && A[i]<hi)) {
ok = false;
}
} else if (A1[i]==A2[i] && A1[i+1]<A2[i]) {
// 3 1 2 or 1 3 2
if (A[i+1]<A[i+2]) {
if (!(A[i]>max(A[i+1],A[i+2]))) {
ok = false;
}
} else if (A[i+1]>A[i+2]) {
if (!(A[i]<min(A[i+1],A[i+2]))) {
ok = false;
}
} else {
assert(false);
}
} else if (A1[i]<A2[i] && A1[i+1]<A2[i]) {
// 1 2 3 or 3 2 1
if (A[i+1]<A[i+2]) {
if (!(A[i]<A[i+1])) {
ok = false;
}
}
if (A[i+1]>A[i+2]) {
if (!(A[i]>A[i+1])) {
ok = false;
}
}
} else {
assert(false);
}
if (ok) {
Set(i,x);
break;
}
}
};
auto bruteR = [&](int i) {
// i, i+1, (i+2)
//cout<<"bruteR: "<<i<<endl;
ask1(i);
ask2(i);
ask1(i+1);
assert(A[i]);
assert(A[i+1]);
vector<int> op;
op.push_back(A[i+1]-A1[i+1]);
op.push_back(A[i+1]+A1[i+1]);
for (int x: op) {
if (x<1 || x>n) continue;
if (isUsed(x)) continue;
A[i+2] = x;
bool ok = true;
if (A1[i]<A2[i] && A1[i+1]<A2[i]) {
// 1 2 3 or 3 2 1
if (A[i]<A[i+1]) {
if (!(A[i+1]<A[i+2])) {
ok = false;
}
} else if (A[i]>A[i+1]) {
if (!(A[i+1]>A[i+2])) {
ok = false;
}
} else {
assert(false);
}
} else if (A1[i]==A2[i] && A1[i+1]<A2[i]) {
//watch(i);
// 1 3 2 or 3 1 2
int lo = min(A[i],A[i+1]);
int hi = max(A[i],A[i+1]);
if (!(lo<=A[i+2] && A[i+2]<=hi)) { //???
ok = false;
}
} else if (A1[i+1]==A2[i] && A1[i]<A2[i]) {
//watch(i);
// 2 3 1
// 2 1 3
int lo = min(A[i+1],A[i+2]);
int hi = max(A[i+1],A[i+2]);
if (!(lo<=A[i] && A[i]<=hi)) {
ok = false;
}
if (A[i]>A[i+1]) {
if (!(A[i+2]>A[i])) {
ok = false;
}
} else if (A[i]<A[i+1]) {
if (!(A[i+2]<A[i])) {
ok = false;
}
} else {
assert(false);
}
} else {
assert(false);
}
if (ok) {
Set(i+2,x);
break;
}
}
// 1 2 3
// 1 3 2
// 2 1 3
// 2 3 1
// 3 1 2
// 3 2 1
};
Set(in,n);
// go left
for (int i=in-1; i>=1; i--) {
ask1(i);
int dif=A1[i];
if (isUsed(A[i+1]-dif)) {
Set(i, A[i+1]+dif);
} else if (isUsed(A[i+1]+dif)) {
Set(i, A[i+1]-dif);
} else {
assert(i+2<=n);
bruteL(i);
assert(A[i]);
}
}
for (int i=in; i<n-1; i++) {
ask1(i);
int dif=A1[i];
if (isUsed(A[i]-dif)) {
Set(i+1, A[i]+dif);
} else if (isUsed(A[i]+dif)) {
Set(i+1, A[i]-dif);
} else {
assert(i-1>=1);
bruteR(i-1);
assert(A[i+1]);
}
}
for (int i=1; i<=n; i++) {
if (!isUsed(i)) {
Set(n,i);
break;
}
}
}
///////////////////////////////////////////////////////////////////////////
/*
int nn;
vector<int> v = {-1,4,6,5,1,7,3,2,9,8};
int query(int s, int t) {
assert(s<=t);
int mx=0;
for (int i=s; i<=t; i++) {
for (int j=i; j<=t; j++) {
mx=max(mx,abs(v[i]-v[j]));
}
}
return mx;
}
void answer(int i, int a) {
A[i]=a;
}
void print() {
cout<<"v: ";
for (int i=1; i<=nn; i++) {
cout<<v[i]<<" ";
}
cout<<endl;
cout<<"A: ";
for (int i=1; i<=nn; i++) {
cout<<A[i]<<" ";
}
cout<<endl;
}
vector<int> rand_perm(int n, int index=1) {
assert(n>=1);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int> a(n);
iota(a.begin(), a.end(), index);
shuffle(a.begin(), a.end(), rng);
return a;
}
vector<int> genV(int n) {
vector<int> v = rand_perm(n, 1);
v.insert(v.begin(), -1);
int i1= -1; int in = -1;
for (int i=1; i<=n; i++) {
if (v[i]==1) i1=i;
if (v[i]==n) in=i;
}
if (i1>in) {
swap(v[i1],v[in]);
}
//v = {-1, 1, 10, 2, 9, 3, 5, 8, 7, 6, 4};
//v = {-1, 2, 1, 5, 7, 8, 3, 10, 9, 6, 4};
//v = {-1, 6, 2, 5, 8, 7, 9, 1, 10, 3, 4 };
// v = {-1,6, 1, 4, 10, 8, 9, 7, 3, 2, 5 };
// v = {-1,2, 9, 1, 3, 10, 5, 6, 4, 7, 8};
return v;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
v = genV(100);
nn = (int)v.size() - 1;
//print();
solve(nn);
print();
for (int i=1; i<=nn; i++) {
assert(A[i]==v[i]);
}
return 0;
}
/*
Compilation message
xylophone.cpp:322:1: warning: "/*" within comment [-Wcomment]
322 | /*
|
xylophone.cpp:245:1: error: unterminated comment
245 | /*
| ^
