// 1) Выберем опорный X (как именно - ?)
// 2) Тернарное разбрасывание в идеале или бинарное
// 3) рекурсивно запускается от "<X" и ">X"
// 4) Худший случай: в качестве опорного элемента всегда берём max или min O(n^2)
// 5) Лучший случай: константный случай W(n)

#include <iostream>
using namespace std;

int cnt = 0;
const int size = 10000;

void qsort(int * l, int * r) {
    ++cnt;
    if (r - l <= 1) return;
    int x = rand() % (r - l);
    int left[size], middle[size], right[size];
    int le = 0, mi = 0, ri = 0;
    cnt += 4;
    for (int i = 0; i < r - l; ++i) {
        cnt += 3;
        if (*(l + i) == *(l + x)) {
            middle[mi++] = *(l + i);
        } else if (*(l + i) < *(l + x)) {
            left[le++] = *(l + i);
        } else {
            right[ri++] = *(l + i);
        }
    }
    cnt++;
    middle[mi++] = *(l + x);
    qsort(left, left + le);
    qsort(right, right + ri);
    for (int i = 0; i < le; ++i) {
        cnt++;
        *(l++) = left[i];
    }
    for (int i = 0; i < mi; ++i) {
        cnt++;
        *(l++) = middle[i];
    }
    for (int i = 0; i < ri; ++i) {
        cnt++;
        *(l++) = right[i];
    }
}

int main() {
    srand(0);
    int arr[size];
    int n;
    cin >> n;
    for (int k = 0; k < 7; ++k) {
        cnt = 0;
        for (int i = 0; i < n; ++i) {
            arr[i] = rand() % 10000;
        }
        qsort(arr, arr + n);
        cout << cnt << endl;
    }
    return 0;
}