#include <bits/stdc++.h>
#include "xylophone.h"
using namespace std;
const int MOD = 1e9 + 7;
const int MAXN = 1e5 + 5;
// int a[MAXN];
// int query(int s, int t){
// int mx = -MAXN, mn = MAXN;
// for(int i= s;i<=t;i++){
// mx = max(mx,a[i]);
// mn = min(mn,a[i]);
// }
// return mx-mn;
// }
void solve(int N){
int nxt[N+2];
for(int i=1;i<N;i++){
nxt[i] = query(i, i+1);
}
int x[N+2];
x[1] = 1;
for(int i=1;i<N-1;i++){
int vl = query(i, i+2);
if(vl == nxt[i] || vl == nxt[i+1]){
x[i+1] = x[i] ^ 1;
} else {
x[i+1] = x[i];
}
}
int b[N+2], c[N+2];
b[1] = 0, c[1] = 0;
for(int i= 1;i<N;i++){
if(x[i] == 1){
b[i+1] = b[i] + nxt[i];
c[i+1] = c[i] - nxt[i];
} else {
b[i+1] = b[i] - nxt[i];
c[i+1] = c[i] + nxt[i];
}
}
int mxb = -MAXN; int mxc = -MAXN;
for(int i = 1;i<=N;i++){
mxb = max(mxb, b[i]);
mxc = max(mxc, c[i]);
}
int diffb = N-mxb;
int diffc = N-mxc;
int idx[2] = {0, 0};
for(int i= 1;i<=N;i++){
b[i] += diffb;
c[i] += diffc;
if(b[i] == 1) idx[0] = i;
if(b[i] == N) idx[1] = i;
}
int ans[N+2];
for(int i= 1;i<=N;i++) {
if(idx[0] < idx[1]){
ans[i] = b[i];
} else {
ans[i] = c[i];
}
answer(i, ans[i]);
}
}
// signed main() {
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
// #ifdef LOCAL
// freopen("input.txt", "r", stdin);
// #endif
// int n;
// cin>>n;
// for(int i= 1;i<=n;i++){
// cin>>a[i];
// }
// solve(n);
// return 0;
// }
