#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int merge_sort_count(vector<int> &a, const int l, const int r)
{
    if (r - l > 1) {
        int mid = l + (r - l) / 2;

        int count = 0;

        count += merge_sort_count(a, l, mid);
        count += merge_sort_count(a, mid, r);

        int i = l;
        for (int j = mid; j < r; j++) {
            while (i < mid && a[i] < a[j]) {
                i++;
            }
            count += i - l;
        }

        inplace_merge(a.begin() + l, 
                      a.begin() + mid, 
                      a.begin() + r);

        return count;
    }

    return 0;
}

int merge_sort_count(vector<int> &a)
{
    return merge_sort_count(a, 0, a.size());
}

int main(void)
{
    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    cout << merge_sort_count(a) << endl;

    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << endl;
    
    return 0;
}