#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 pq_Push(PQueue queue, int32_t value, int32_t index) {
  int32_t *heap = queue->heap;
  int32_t *indexes = queue->indexes;
  int32_t heapSize = queue->size;
  queue->heap[queue->size] = value;
  queue->indexes[queue->size] = index;
  queue->size++;
  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])) {
    checker = 0;
    if((index << 1) + 2 >= heapSize) {
      swap(heap, index, (index << 1) + 1);
      swap(indexes, index, (index << 1) + 1);
      index <<= 1;
      index++;
      checker = 1;
    }
    else if((index << 1) + 2 < heapSize && heap[(index << 1) + 2] >= heap[(index << 1) + 1]) {
      swap(heap, index, (index << 1) + 1);
      swap(indexes, index, (index << 1) + 1);
      index <<= 1;
      index++;
      checker = 1;
    }
    else if((index << 1) + 2 < heapSize && heap[(index << 1) + 1] >= heap[(index << 1) + 2]) {
      swap(heap, index, (index << 1) + 2);
      swap(indexes, index, (index << 1) + 2);
      index <<= 1;
      index += 2;
      checker = 1;
    }
    if(!checker)
      break;
  }
}

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+");
    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));
        pq_DeleteHead(priority);
    }
    pq_Delete(priority);
    fclose(fd);
    fclose(fr);
}