#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
static int A[5000];
vector<ii> locations;
void findNext2(int N, int top, int bot, int prevLoc, bool gr1);
void findNext1(int N, int top, int bot = 1, int prevLoc = 1, bool gr1 = false, bool exl = false) {
if (top == bot) return;
int mid;
int low = bot, high = top;
int prev = query(low, high);
while (low != high) {
mid = (low+high)/2;
int res = query(bot, mid);
if (res == prev) high = mid;
else low = mid+1;
}
locations.push_back({prevLoc+prev*(gr1?-1:1), low});
findNext1(N, top, low, prevLoc+prev*(gr1?-1:1), !gr1, true);
findNext2(N, low, bot + exl, prevLoc+prev*(gr1?-1:1), !gr1);
}
void findNext2(int N, int top, int bot, int prevLoc = 1, bool gr1 = false ) {
if (top == bot) return;
int mid;
int low = bot, high = top;
int prev = query(low, high);
while (low != high) {
mid = (low+high+1)/2;
int res = query(mid, top);
if (res == prev) low = mid;
else high = mid-1;
}
locations.push_back({prevLoc+prev*(gr1?-1:1), low});
findNext1(N, top-1, low, prevLoc+prev*(gr1?-1:1), !gr1, true);
findNext2(N, low, bot, prevLoc+prev*(gr1?-1:1), !gr1);
}
void solve(int N) {
findNext1(N, N);
sort(locations.begin(), locations.end());
bool oppdir = (locations[0].second > locations.back().second);
for (int i = 0; i < N; i++) {
answer(locations[i].second, (oppdir ? N-i : i + 1));
}
}
