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

#define INITIAL_CAPACITY (1<<19)

struct PQueue_t {
  int32_t *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(int32_t) * INITIAL_CAPACITY);
  queue->indexes = malloc(sizeof(int32_t) * INITIAL_CAPACITY);
  queue->size = 0;
  return queue;
}

void fswap(int32_t *array, int32_t a, int32_t b) {
  int32_t 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]) {
            swap(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]) {
            swap(queue->heap, index, index >> 1);
            swap(queue->indexes, index, index >> 1);
            pushElement(queue, index >> 1);
        }
    }
}

void pq_Push(PQueue queue, int32_t value, int32_t index) {
  queue->heap[queue->size] = value;
  queue->indexes[queue->size] = index;
  pushElement(queue, queue->size);
  queue->size++;
//   if(!(queue->size & 1)) {
//       heapSize--;
//   }
//   while(heapSize > 0 && heap[heapSize] <= heap[heapSize >> 1]) {
//     swap(heap, heapSize, heapSize >> 1);
//     swap(indexes, heapSize, heapSize >> 1);
//     heapSize >>= 1;
//   }
}

void pq_DeleteHead(PQueue queue) {
  int32_t *heap = queue->heap;
  int32_t *indexes = queue->indexes;
  int32_t heapSize = queue->size;
  int32_t index = 0;
  //int8_t checker = 0;
  swap(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) {
      swap(heap, index, (index << 1) + 1);
      swap(indexes, index, (index << 1) + 1);
      index <<= 1;
      index++;
    }
    else if(heap[(index << 1) + 2] >= heap[(index << 1) + 1]) {
      swap(heap, index, (index << 1) + 1);
      swap(indexes, index, (index << 1) + 1);
      index <<= 1;
      index++;
    }
    else {
      swap(heap, index, (index << 1) + 2);
      swap(indexes, index, (index << 1) + 2);
      index <<= 1;
      index += 2;
    }
  }
//   int8_t ok = 0;
//   for(int32_t i = 0; i < heapSize; i++) {
//       if(heap[i] < heap[i >> 1]) {
//           ok = 1;
//           printf("%d %d\n", i, i >> 1);
//           break;
//       }
//   }
//   if(ok) {
//     for(int32_t i = 0; i < heapSize; i++) {
//         printf("%d %d\n", i, heap[i]);
//     }
//     exit(0);
//   }
}

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

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

void pq_View(PQueue queue) {
  for(size_t i = 0; i < queue->size; i++) {
    printf("%d ", queue->heap[i]);
  }
  printf("\n");
  for(size_t i = 0; i < queue->size; i++) {
    printf("%d ", queue->indexes[i]);
  }
  printf("\n\n");
}

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) * 10000);
    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, 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);
    }
    pq_Delete(priority);
    fclose(fd);
    fclose(fr);
}