#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
#include <math.h>

#include "quicksort.h"

using namespace std;

int findMedian(vector<int> &A, int p, int r) {

  int m = (p+r)/2;

  if (A[p] >= A[m]) {
      if (A[m] > A[r]) {
          return m;
      } else if (A[p] > A[r]) {
          return r;
      } else {
          return p;
      }
  } else {
      if (A[p] > A[r]) {
          return p;
      } else if (A[m] > A[r]) {
          return r;
      } else {
          return m;
      }
    }
}

int partition(vector<int> &A, int p, int r) {

    int m = findMedian(A, p, r);
    swap(A[m], A[r]);

    int pivot = A[r];
    int i = (p-1);

    for (int j = p; j <= r-1; j++) {

        if (A[j] <= pivot) {
            i = i + 1;
            swap(A[i], A[j]);
        }
    }
    swap(A[i+1], A[r]);
    return i+1;
}

void quicksort(vector<int> &A, int p, int r, int &count) {
    if (p < r) {
        count = count + (r - p);
        int q = partition(A, p, r);

        quicksort(A, p, q - 1, count);
        quicksort(A, q + 1, r, count);
    }
}

int main()
{

    vector<int> result;

    int n, j;
    ifstream f("1.txt");
    f >> n;

    for (int i = 0; i < n; i++) {
        f >> j;
        result.push_back(j);
    }

    int count = 0;
    quicksort(result, 0, result.size()-1, count);

    for (int i = 0; i < result.size(); i++) {
        cout << result[i] << " ";
    }
    cout << "\n";
    cout << count << "\n";

    return 0;
}