#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#define INITIAL_CAPACITY (1<<20)

struct PQueue_t {
  double *heap;
  int32_t *indexes;
  int32_t size;
};

typedef struct PQueue_t *PQueue;

PQueue pq_New(void) {
  PQueue queue = malloc(sizeof(struct PQueue_t));
  queue->heap = malloc(sizeof(double) * INITIAL_CAPACITY);
  queue->indexes = malloc(sizeof(int32_t) * INITIAL_CAPACITY);
  queue->size = 0;
  return queue;
}

void fswap(double *array, int32_t a, int32_t b) {
  double aux = array[a];
  array[a] = array[b];
  array[b] = aux;
}

void swap(int32_t *array, int32_t a, int32_t b) {
  int32_t aux = array[a];
  array[a] = array[b];
  array[b] = aux;
}

void pushElement(PQueue queue, int32_t index) {
    if(!index) {
        return ;
    }
    if(!(index & 1)) {
        if(queue->heap[index] <= queue->heap[(index - 1) >> 1]) {
            fswap(queue->heap, index, (index - 1) >> 1);
            swap(queue->indexes, index, (index - 1) >> 1);
            pushElement(queue, (index - 1) >> 1);
        }
    }
    else {
        if(queue->heap[index] <= queue->heap[index >> 1]) {
            fswap(queue->heap, index, index >> 1);
            swap(queue->indexes, index, index >> 1);
            pushElement(queue, index >> 1);
        }
    }
}

void pq_Push(PQueue queue, double value, int32_t index) {
  queue->heap[queue->size] = value;
  queue->indexes[queue->size] = index;
  pushElement(queue, queue->size);
  queue->size++;
}

void pq_DeleteHead(PQueue queue) {
  double *heap = queue->heap;
  int32_t *indexes = queue->indexes;
  int32_t heapSize = queue->size;
  int32_t index = 0;
  fswap(heap, 0, heapSize - 1);
  swap(indexes, 0, heapSize - 1);
  queue->size--;
  heapSize--;
  while(((index << 1) + 1 < heapSize && heap[index] > heap[(index << 1) + 1]) ||
        ((index << 1) + 2 < heapSize && heap[index] > heap[(index << 1) + 2])) {
    if((index << 1) + 2 >= heapSize) {
      fswap(heap, index, (index << 1) + 1);
      swap(indexes, index, (index << 1) + 1);
      index <<= 1;
      index++;
    }
    else if(heap[(index << 1) + 2] >= heap[(index << 1) + 1]) {
      fswap(heap, index, (index << 1) + 1);
      swap(indexes, index, (index << 1) + 1);
      index <<= 1;
      index++;
    }
    else {
      fswap(heap, index, (index << 1) + 2);
      swap(indexes, index, (index << 1) + 2);
      index <<= 1;
      index += 2;
    }
  }
}

int32_t pq_GetMinValueIndex(PQueue queue) {
  if(!queue->size)
    return -1;
  return queue->indexes[0];
}

double pq_GetMinValue(PQueue queue) {
  if(!queue->size)
    return -1;
  return queue->heap[0];
}

void pq_Delete(PQueue queue) {
  free(queue->heap);
  free(queue->indexes);
}

int main() {
    FILE *fd = fopen("algsort.in", "r+");
    FILE *fr = fopen("algsort.out", "w+");
    int32_t *array = malloc(sizeof(int32_t) * 500020);
    int32_t index = 0;
    PQueue priority = pq_New();
    int32_t n, a;
    fscanf(fd, "%d", &n);
    for(int32_t i = 0; i < n; i++) {
        fscanf(fd, "%d", &a);
        pq_Push(priority, (int32_t)a, i);
    }
    for(int32_t i = 0; i < n; i++) {
        fprintf(fr, "%d ", (int32_t)pq_GetMinValue(priority));
        array[index++] = (int32_t)pq_GetMinValue(priority);
        pq_DeleteHead(priority);
    }
    // for(int32_t i = 0; i < n - 1; i++) {
    //     if(priority->heap[i] > priority->heap[i + 1]) {
    //         printf("Wrong %f %f %f", i, priority->heap[i], priority->heap[i + 1]);
    //         exit(0);
    //     }
    // }
    pq_Delete(priority);
    fclose(fd);
    fclose(fr);
}