#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define ff first
#define sc second
#define pb push_back
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define ull unsigned long long
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rngl(chrono::steady_clock::now().time_since_epoch().count());
// #define int long long
// #define int unsigned long long
// #define ordered_set(T) tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>
// #define ordered_multiset(T) tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>
// const ll mod = 1e9 + 7;
// const ll mod = 998244353;
const ll inf = 1e9;
const ll biginf = 1e18;
const int maxN = 5 * 1e5 + 15;
void solve(int n) {
int a[n + 1], b[n + 1];
for (int i = 1; i <= n - 1; i++) a[i] = query(i, i + 1);
for (int i = 1; i <= n - 2; i++) b[i] = query(i, i + 2);
bool diff[n + 1]; diff[1] = 1;
for (int i = 2; i < n; i++) {
if (a[i - 1] + a[i] == b[i - 1]) diff[i] = diff[i - 1];
else diff[i] = (diff[i - 1] ^ 1);
}
vector<int> ans;
int mn = 1, cur = 1;
for (int i = 2; i <= n; i++) {
if (flg[i - 1]) {
cur -= a[i - 1]; mn = min(mn, cur); ans.pb(cur);
} else {
cur += a[i - 1]; mn = min(mn, cur); ans.pb(cur);
}
}
for (int &i : cur) i += 1 - mn;
int pos1, posn;
for (int i = 0; i < ans.size(); i++) {
if (ans[i] == 1) pos1 = i;
if (ans[i] == n) posn = i;
}
if (pos1 < posn) {
for (int i = 0; i < ans.size(); i++)
answer(i + 1, ans[i]);
return;
}
ans.clear();
mn = 1; cur = 1;
for (int i = 2; i <= n; i++) {
if (flg[i - 1]) {
cur += a[i - 1]; mn = min(mn, cur); ans.pb(cur);
} else {
cur -= a[i - 1]; mn = min(mn, cur); ans.pb(cur);
}
}
for (int &i : cur) i += 1 - mn;
for (int i = 0; i < ans.size(); i++)
answer(i + 1, ans[i]);
}
