#include <bits/stdc++.h>

struct nod {
  int val;
  nod *l, *r;
};

class list {
private:
  /* Noduri auxiliare. */
  nod *begin;
  nod *end;

  int nr(nod* curr) {
    if (curr == end) {
      return 0;
    }
    return 1 + nr(curr -> r);
  }

  void afis(nod* curr) {
    if (curr != end) {
      fprintf(stderr, "%d, ", curr -> val);
      afis(curr -> r);
    }
  }

public:
  /** Initializeaza lista. **/
  list() {
    begin = new nod;
    end = new nod;

    begin -> l = NULL;
    begin -> r = end;

    end -> l = begin;
    end -> r = NULL;
  }

  /** Da-mi marimea listei. **/
  int size() {
    return nr(begin -> r);
  }

  int empty() {
    return size() == 0;
  }

  /** Adauga la finalul listei valoarea "x". **/
  void push_back(int x) {
    nod *nou = new nod;
    nou -> val = x;
    nou -> l = end -> l;
    nou -> r = end;
    end -> l -> r = nou;
    end -> l = nou;
  }

  /** Adauga la inceputul listei valoarea "x". **/
  void push_front(int x) {
    nod *nou = new nod;
    nou -> val = x;
    nou -> r = begin -> r;
    nou -> l = begin;
    begin -> r -> l = nou;
    begin -> r = nou;
  }

  /** Sterge elementul aflat la finalul listei. **/
  void pop_back() {
    end -> l = end -> l -> l;
  }

  /** Sterge elementul aflat la inceputul listei. **/
  void pop_front() {
    begin -> r = begin -> r -> r;
  }

  /** Sterge o aparitie a valorii "x". **/
  void erase(int x) {
    nod* curr = begin -> r;

    while (curr -> val != x) {
      curr = curr -> r;
    }
    curr -> l -> r = curr -> r;
    curr -> r -> l = curr -> l;
  }

  /** Da-mi elementul afla la inceputul listei. **/
  int front() {
    return begin -> r -> val;
  }

  /** Da-mi elementul aflat la finalul listei. **/
  int back() {
    return end -> l -> val;
  }

  /** Sorteaza lista dupa un "cmp" (l-am facut "bool" ca sa se simta Andrei bine). **/
  void sort(bool cmp(int, int)) {
    for (nod* walk = begin -> r; walk != end; walk = walk -> r) {
      for (nod* curr = walk -> r; curr != end; curr = curr -> r) {
        if (cmp(curr -> val, walk -> val)) {
          int tmp = curr -> val;
          curr -> val = walk -> val;
          walk -> val = tmp;
        }
      }
    }
  }

  /** Afiseaza lista de la stanga la dreapta. **/
  void write() {
    afis(begin -> r);
    fprintf(stderr, "\n");
  }
};

bool crescator(int a, int b) {
  return a < b;
}

bool descrescator(int a, int b) {
  return a > b;
}

int main(void) {
  list val;

  assert(val.empty());

  /** Probe. **/
  val.push_back(3);
  val.push_back(5);
  val.push_back(7);
  val.push_back(10);
  val.push_front(20);
  val.push_front(40);

  val.pop_front();
  val.pop_back();
  val.pop_back();

  val.push_back(100);
  val.push_back(300);
  val.push_back(400);

  val.erase(400);

  val.write();

  val.sort(crescator);
  val.write();

  val.sort(descrescator);
  val.write();

  fprintf(stderr, "%d\n", val.front());

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