#include <time.h>
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <limits.h>

#define Nadejde 2000000
#define Dragoste 4096
#define MAX_LEVEL 20
#define Randomize -524289

int level;             // nivelul maxim din structura.
int bufPtr;            // primul slot nealocat.
int sl[Nadejde];       // zona de memorie prealocata.
int pos = Dragoste;    // pozitia in "buff".
int update[MAX_LEVEL]; // folosit in timpul inserarii.
char c, buff[Dragoste];

/** Ia urmatorul caracter din "f". **/
char getChar(FILE *f) {
  if (pos == Dragoste) {
    fread(buff, 1, Dragoste, f);
    pos = 0;
  }
  return buff[pos++];
}

/** Citeste urmatorul numar din "f". **/
void freef(FILE *f, const char *arg, int *result) {
  *result = 0;
  do {
    c = getChar(f);
  } while (!isdigit(c));
  do {
    *result = (*result << 3) + (*result << 1) + c - '0';
    c = getChar(f);
  } while (isdigit(c));
}

/** Initializeaza structura. **/
void init() {
  /* Capul listei are valoarea -INF si MAX_LEVEL pointeri catre coada listei. */
  /* Coada listei are valoare INF si 0 pointeri. */
  sl[0] = -INT_MAX;
  sl[MAX_LEVEL + 1] = INT_MAX;

  int i;
  for (i = 1; i <= MAX_LEVEL; i++) {
    sl[i] = MAX_LEVEL + 1;
  }
  bufPtr = MAX_LEVEL + 2;
  level = 1;
}

/** Da-mi un nivel random. **/
int randomLevel() {
  int l = 1, r;
  for (l = 1, r = rand() & Randomize; r & 1; r >>= 1) {
    l++;
  }
  return l;
}

/** Insereaza valorea "x" in structura. **/
void insert(int x) {
  int l, pos = 0;
  for (l = level - 1; l >= 0; l--) {
    while (sl[sl[pos + l + 1]] < x) {
      pos = sl[pos + l + 1];
    }
    update[l] = pos;
  }
  pos = sl[pos + 1];

  int newLevel = randomLevel();
  if (newLevel > level) {
    for (l = level; l < newLevel; l++) {
      update[l] = 0;
    }
    level = newLevel;
  }

  sl[bufPtr] = x;
  for (l = 0; l < newLevel; l++) {
    sl[bufPtr + l + 1] = sl[update[l] + l + 1];
    sl[update[l] + l + 1] = bufPtr;
  }
  bufPtr += newLevel + 1;
}

int main(void) {
  int N, i, val;
  FILE *f = fopen("algsort.in", "r");

  init();
  srand(time(NULL));

  /* Citeste vectorul initial. */
  freef(f, "%d", &N);
  for (i = 0; i < N; i++) {
    freef(f, "%d", &val);
    insert(val);
  }
  fclose(f);

  f = fopen("algsort.out", "w");

  /* Sorteaza folosind Skip-Lists. */
  int pos = sl[1];
  while (sl[pos] != INT_MAX) {
    fprintf(f, "%d ", sl[pos]);
    pos = sl[pos + 1];
  }
  fputc('\n', f);
  fclose(f);

  /// Multumim Doamne!
  puts("Doamne ajuta!");
  return 0;
}