#include <stdio.h>

#include <stdlib.h>

#include <stdint.h>

#define SWAP_F(a, b)                                                           \
  do {                                                                         \
    float temp;                                                                \
    SWAP(a, b, temp);                                                          \
  } while (0)

#define SWAP_I32(a, b)                                                         \
  do {                                                                         \
    int32_t temp;                                                              \
    SWAP(a, b, temp);                                                          \
  } while (0)

#define SWAP(a, b, temp)                                                      \
  do {                                                                         \
    temp = a;                                                                  \
    a = b;                                                                     \
    b = temp;                                                                  \
  } while (0)

#define INITIAL_CAPACITY (1<<20)



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++;

}



void pq_DeleteHead(PQueue queue) {
    int32_t s;
  int32_t node;
  int32_t smallestChild;
  int32_t largestChild;

  s = queue->size - 1;
  SWAP_I32(queue->heap[0], queue->heap[s]);
  SWAP_I32(queue->indexes[0], queue->indexes[s]);
  queue->size--;
  node = 0;

  while (1) {
    smallestChild = ((node + 1) << 1) - 1;
    largestChild = smallestChild + 1;
    if (largestChild < s &&
        queue->heap[largestChild] < queue->heap[smallestChild]) {
      SWAP_I32(smallestChild, largestChild);
    }
    if (smallestChild < s && queue->heap[node] > queue->heap[smallestChild]) {
      SWAP_I32(queue->heap[node], queue->heap[smallestChild]);
      SWAP_I32(queue->indexes[node], queue->indexes[smallestChild]);
      node = smallestChild;
    } else {
      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+");

    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, 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);

}