#include "monster.h"

#include <bits/stdc++.h>
using namespace std;

vector<int> Solve(int N) {
  int query_count = 0;
  map<pair<int, int>, int> memo;
  const auto Compare = [&](int a, int b) {
    if (memo.count({a, b})) return memo[{a, b}];
    query_count++;
    int foo = Query(a, b);
    memo[{a, b}] = foo;
    memo[{b, a}] = 1 - foo;
    return foo;
  };

  const auto MergeSort = [&](const auto &self, int l, int r) -> vector<int> {
    if (l == r) return {l};
    int md = (l + r) / 2;
    vector<int> lft = self(self, l, md);
    vector<int> rgt = self(self, md + 1, r);

    vector<int> res;
    reverse(begin(lft), end(lft));
    reverse(begin(rgt), end(rgt));

    while (!lft.empty() && !rgt.empty()) {
      if (Compare(lft.back(), rgt.back())) {
        res.emplace_back(lft.back());
        lft.pop_back();
      } else {
        res.emplace_back(rgt.back());
        rgt.pop_back();
      }
    }
    while (!lft.empty()) {
      res.emplace_back(lft.back());
      lft.pop_back();
    }
    while (!rgt.empty()) {
      res.emplace_back(rgt.back());
      rgt.pop_back();
    }

    return res;
  };

  vector<int> almostSorted = MergeSort(MergeSort, 0, N - 1);

  const auto FindMaxSpecial = [&](int start) -> int {
    for (int i = start + 1; i + 2 < N; i++) {
      if (Compare(almostSorted[i], almostSorted[i + 2])) {
        return i + 1;
      }
    }
    return N - 1;
  };

  vector<int> sorted;
  vector<int> done(N);

  int mxId = -1;
  int last = 0;

  if (Compare(almostSorted[0], almostSorted[2])) {
    // - 3 4 1 2 ..
    // - 3 0 1 2 ..
    if (Compare(almostSorted[1], almostSorted[3])) {
      mxId = 1;
    } else {
      mxId = 0;
    }
  } else {
    // - 3 4 5 6 ...
    // - 3 4 5 2 ...
    // - 3 4 5 0 ...
    // - 3 1 2 0 ...
    // - 3 4 2 0 ...
    if (Compare(almostSorted[0], almostSorted[3])) {
      // - 3 4 5 0 ...
      // - 3 1 2 0 ...
      // - 3 4 2 0 ...
      if (Compare(almostSorted[1], almostSorted[3])) {
        // - 3 4 5 0 1
        // - 3 4 5 1 2 ...
        // - 3 4 2 0 1 ...
        // - 4 5 3 0 1 ...
        // - 4 2 3 0 1 ...
        assert(N >= 5);
        if (!Compare(almostSorted[1], almostSorted[4])) {
          // - 5 3 4 1 2 ...
          mxId = 4;
          last = 3;
          done[0] = done[1] = done[2] = 1;
          sorted.emplace_back(almostSorted[0]);
          sorted.emplace_back(almostSorted[2]);
          sorted.emplace_back(almostSorted[1]);
        } else if (Compare(almostSorted[2], almostSorted[4])) {
          // - 3 4 5 0 1 ...
          // - 3 4 5 1 2 ...
          // - 4 5 3 0 1 ...
          // - 5 3 4 0 1 ...
          if (Compare(almostSorted[0], almostSorted[4])) {
            // - 3 4 5 0 1 2 ...
            // - 4 5 3 0 1 2 ...
            // - 5 3 4 0 1 2 ...
            assert(N >= 6);
            last = 3;
            mxId = FindMaxSpecial(3);
            if (!Compare(almostSorted[0], almostSorted[mxId])) {
              // - 3 4 5 0 1 2 ...
              done[0] = done[1] = done[2] = 1;
              sorted.emplace_back(almostSorted[2]);
              sorted.emplace_back(almostSorted[1]);
              sorted.emplace_back(almostSorted[0]);
            } else if (!Compare(almostSorted[1], almostSorted[mxId])) {
              // - 5 3 4 0 1 2 ...
              done[0] = done[1] = done[2] = 1;
              sorted.emplace_back(almostSorted[0]);
              sorted.emplace_back(almostSorted[2]);
              sorted.emplace_back(almostSorted[1]);
            } else if (!Compare(almostSorted[2], almostSorted[mxId])) {
              // - 4 5 3 0 1 2 ...
              done[0] = done[1] = done[2] = 1;
              sorted.emplace_back(almostSorted[1]);
              sorted.emplace_back(almostSorted[0]);
              sorted.emplace_back(almostSorted[2]);
            }
          } else {
            // - 3 4 5 1 2 ...
            mxId = 2;
          }
        } else {
          // - 3 4 2 0 1 ...
          mxId = 1;
        }
      } else {
        // - 3 1 2 0 ...
        mxId = 0;
      }
    } else {
      // - 3 4 5 6 ...
      // - 3 4 5 2 ...
      mxId = FindMaxSpecial(0);
    }
  }

  for (int i = mxId; i >= 0; i--) if (!done[i]) {
    done[i] = 1;
    sorted.emplace_back(almostSorted[i]);
  }
  for (int i = mxId + 1; i < N; i++) {
    if (!Compare(almostSorted[last], almostSorted[i])) {
      last = i;
      while (!done[last]) {
        done[last] = 1;
        sorted.emplace_back(almostSorted[last]);
        last--;
      }
      last++;
    }
  }

  assert(sorted.size() == N);
  vector<int> ans(N);
  for (int i = 0; i < N; i++) {
    ans[sorted[i]] = i;
  }
  for (int i = 0; i < N; i++) {
    ans[i] = N - 1 - ans[i];
  }
  return ans;
}