const int NMAX = 1000000000;

int n;
int p[NMAX + 1];

int ops;
void bubble(int gap) {
    bool ok = true;
    while (ok) {
        ok = false;
        for (int i = 1; i <= n - gap; ++ i)
            if (p[i] > p[i + gap]) {
                swap(p[i], p[i + gap]);
                ++ ops;
                ok = true;
            }
    }
}

void bubblesort() {
    int gap = n;
    while (gap) {
        bubble(gap);
        gap /= 2;
    }
}