#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <iostream>
using namespace std;
void read_array(int* x, int x_size) {
    for (int i = 0; i < x_size; ++i) {
        scanf("%d", &x[i]);
    }
}
void write_array(int* x, int x_size) {
    for (int i = 0; i < x_size; ++i) {
        printf("%d ", x[i]);
    }
}
void sort_array(int* x, int x_size,int& x_c) {
    if (x_size == 1)
        return;

    int a_size = x_size / 2;
    int b_size = x_size - a_size;
    int* b = x + a_size;
    int* c = new int[x_size];
    int a_i = 0;
    int b_i = 0;
    sort_array(x, a_size,x_c);
    sort_array(b, b_size,x_c);
    for (int c_i = 0; c_i < x_size; ++c_i) {
        x_c += 1;
        if (a_i == a_size) {
            c[c_i] = b[b_i];
            b_i += 1;
            continue;
        }
        if (b_i == b_size) {
            c[c_i] = x[a_i];
            a_i += 1;
            continue;
        }
        if (x[a_i] >= b[b_i]) {
            c[c_i] = b[b_i];
            b_i += 1;
        }
        else {
            c[c_i] = x[a_i];
            a_i += 1;
        }
    }
    for (int i = 0; i < x_size; ++i) {
        x[i] = c[i];
    }
    delete[] c;
}
void sort_array_bubbl(int* x, int x_size,int& x_d) {
    for (int i = 1; i < x_size; ++i) {
        for (int j = 1; j < x_size; ++j) {
            if (x[j] < x[j - 1]) {
                swap(x[j], x[j - 1]);
            }
            x_d += 1;
        }
    }
}
int main() {
    int n;
    cin >> n;
    int* a = new int[n];
    int* b = new int[n];
    int c = 0;
    int d = 0;
    read_array(a, n);
    for (int i = 0; i < n; ++i) {
        b[i] = a[i];
    }
    sort_array(a, n, c);
    sort_array_bubbl(b, n, d);
    cout << "a"<< endl;
    write_array(a, n);
    cout << endl;
    cout << "c =="<<c<<endl;
    cout << "b"<< endl;
    write_array(b, n);
    cout << endl;
    cout << "d=="<< d;
    delete[]a;
    delete[]b;
    return 0;
}