#include <iostream>
#include <vector>
#include <limits>
#include <memory>
#include <cassert>

// This is the quick-select from https://cp-algorithms.com/sequences/k-th.html
template <class T>
T order_statistics (std::vector<T> a, unsigned n, unsigned k)
{
    using std::swap;
    for (unsigned l=1, r=n; ; )
    {
        if (r <= l+1)
        {
            // the current part size is either 1 or 2, so it is easy to find the answer
            if (r == l+1 && a[r] < a[l])
                swap (a[l], a[r]);
            return a[k];
        }

        // ordering a[l], a[l+1], a[r]
        unsigned mid = (l + r) >> 1;
        swap (a[mid], a[l+1]);
        if (a[l] > a[r])
            swap (a[l], a[r]);
        if (a[l+1] > a[r])
            swap (a[l+1], a[r]);
        if (a[l] > a[l+1])
            swap (a[l], a[l+1]);

        // performing division
        // barrier is a[l + 1], i.e. median among a[l], a[l + 1], a[r]
        unsigned
            i = l+1,
            j = r;
        const T
            cur = a[l+1];
        for (;;)
        {
            while (a[++i] < cur) ;
            while (a[--j] > cur) ;
            if (i > j)
                break;
            swap (a[i], a[j]);
        }

        // inserting the barrier
        a[l+1] = a[j];
        a[j] = cur;

        // we continue to work in that part, which must contain the required element
        if (j >= k)
            r = j-1;
        if (j <= k)
            l = i;
    }
}


struct Amorphous {
  // Idea: M. Douglas McIlroy
  // Generally breaks single-pivot quicksort
  // See https://www.cs.dartmouth.edu/~doug/aqsort.c
  int uid;
  std::shared_ptr<int> val;
  std::shared_ptr<int> cprCt;
  static int count;
  static int evap;
  static long long overallCprCt;

  Amorphous()
    :uid { count++ },
     val { new int { std::numeric_limits<int>::max() } },
     cprCt { new int { 0 } }
  {}

  int freeze() const {
    if (*val >= evap)
      *val = evap++;
    return *val;
  }

  bool operator < (const Amorphous& o) const {
    ++overallCprCt;
    if (std::min(*val, *o.val) < evap)
      return *val < *o.val;
    if (++*cprCt < ++*o.cprCt) {
      ++*cprCt;
      *o.val = evap++;
    }
    else {
      ++*o.cprCt;
      *val = evap++;
    }
    return *val < *o.val;
  }

  bool operator > (const Amorphous& o) const {
    return o < *this;
  }
};

int Amorphous::count;
int Amorphous::evap;
long long Amorphous::overallCprCt;

struct Int {
  int v;

  Int(int val)
    :v { val }
  {}

  static long long overallCprCt;

  bool operator < (Int o) const {
    ++overallCprCt;
    return v < o.v;
  }

  bool operator > (Int o) const {
    return o < *this;
  }
};

long long Int::overallCprCt = 0;

int main() {
  using namespace std;
  ios::sync_with_stdio(false);

  int n;
  cin >> n;
  assert(n >= 2);
  vector<Amorphous> v;
  v.reserve(n+1);
  for (int i = 0; i <= n; ++i)
    v.emplace_back();
  order_statistics(v, n, n - 2);
  cout << "total comparisons: " << Amorphous::overallCprCt << '\n';
  cout << "show input?\n";
  int flag;
  cin >> flag;
  if (!flag)
    return 0;
  vector<Int> s;
  s.reserve(n+1);
  for (Amorphous& x : v)
    s.emplace_back(x.freeze());
  order_statistics(s, n, n - 2);
  assert(Int::overallCprCt == Amorphous::overallCprCt);
  for (Int x : s)
    cout << x.v << ' ';
  cout << '\n';

  return 0;
}