Золотая середина

# Золотая середина

#include <iostream>
#include <fstream>


void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}


void siftDownMax(int *heap, int i, int size) {
    int left, right, j;
    while (2 * i + 1 < size) {
        left = 2 * i + 1;
        right = 2 * i + 2;
        j = left;
        if (right < size and heap[right] > heap[left])
            j = right;
        if (heap[i] >= heap[j])
            break;
        swap(&heap[i], &heap[j]);
        i = j;
    }
}


void siftDownMin(int *heap, int i, int size) {
    int left, right, j;
    while (2 * i + 1 < size) {
        left = 2 * i + 1;
        right = 2 * i + 2;
        j = left;
        if (right < size and heap[right] < heap[left])
            j = right;
        if (heap[i] <= heap[j])
            break;
        swap(&heap[i], &heap[j]);
        i = j;
    }
}


void siftUpMax(int *heap, int i) {
    while (heap[i] > heap[(i - 1) / 2]) {
        swap(&heap[i], &heap[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}


void siftUpMin(int *heap, int i) {
    while (heap[i] < heap[(i - 1) / 2]) {
        swap(&heap[i], &heap[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}


int getPopMin(int *heap, int *size) {
    int min = heap[0];
    heap[0] = heap[*size - 1];
    *size = *size - 1;
    siftDownMin(heap, 0, *size);
    return min;
}


int getPopMax(int *heap, int *size) {
    int max = heap[0];
    heap[0] = heap[*size - 1];
    *size = *size - 1;
    siftDownMax(heap, 0, *size);
    return max;
}


void addToMax(int *heap, int key, int *size) {
    *size = *size + 1;
    heap[*size - 1] = key;
    siftUpMax(heap, *size - 1);
}


void addToMin(int *heap, int key, int *size) {
    *size = *size + 1;
    heap[*size - 1] = key;
    siftUpMin(heap, *size - 1);
}


int main() {
    std::ifstream fin("input.txt");
    std::ofstream fout("output.txt");

    int n;
    fin >> n;

    int heapMax[n / 2 + 2], sizeMax = 0;
    int heapMin[n / 2 + 2], sizeMin = 0;

    int input;
    fin >> input;
    addToMax(heapMax, input, &sizeMax);
    fout << heapMax[0] << " ";

    for (int i = 0; i < n - 1; i++) {
        fin >> input;
        if (input > heapMax[0]) {
            addToMin(heapMin, input, &sizeMin);
        }
        else {
            addToMax(heapMax, input, &sizeMax);
        }

        if (sizeMin > sizeMax) {
            int root = getPopMin(heapMin, &sizeMin);
            addToMax(heapMax, root, &sizeMax);
        }
        else if (sizeMax - 1 > sizeMin) {
            int root = getPopMax(heapMax, &sizeMax);
            addToMin(heapMin, root, &sizeMin);
        }
        fout << heapMax[0] << " ";
    }

    fin.close();
    fout.close();


    return 0;
}