#include <vector>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

vector<int> v;
unsigned long long int comparisons;

inline void _swap(int& x, int& y) {int aux = x; x = y; y = aux;}
int partition(int left, int right, int pIndex)
{
    int pValue, i, j;

    pValue = v[pIndex];
    _swap(v[left], v[pIndex]);

    for(i = j = left + 1; j <= right; ++j)
    {
	if(v[j] < pValue)
	{
	    swap(v[j], v[i]);
	    ++i;
	}
    }
    _swap(v[left], v[i-1]);

    return i - 1;    
}

inline int medianOfThree(int left, int middle, int right)
{
    if(v[left] > v[middle])
    {
	if(v[middle] > v[right])    return middle;
        else if(v[left] < v[right]) return left;
        else                        return right;
	     
    }    
    else {
	     if(v[middle] < v[right])    return middle;
             else if(v[left] > v[right]) return right;
	     else                        return left;
         }
}

inline void QuickSort(int left, int right)
{
    if(left >= right) return;
    comparisons += right - left;
    if(1 == right - left)
    {
	if(v[left] > v[right])
	{
            _swap(v[left], v[right]);
	}
        return;
    } 
   
    int pIndex = partition(left, right, medianOfThree(left, (left + right) >> 1, right));

    QuickSort(left, pIndex - 1);
    QuickSort(pIndex + 1, right);
}

int main()
{
    int N;
    ifstream in("algsort.in");
    ofstream out("algsort.out");

    in >> N;
    copy(istream_iterator<int>(in), istream_iterator<int>(), back_inserter(v));

    QuickSort(0, v.size() - 1);

    copy(v.begin(), v.end(), ostream_iterator<int>(out, " "));
    out << '\n';

    cout << comparisons << '\n';

    return EXIT_SUCCESS;
}