/** ComparableList ::= EmptyComparableList | ConsComparableList(Comparable, ComparableList). */
abstract class ComparableList { 
  /** Sorts this ComparableList into ascending (non-descending) order. */
  abstract ComparableList sort();
  /** Adds the Comparable n to the front of this ComparableList */
  ComparableList cons(Comparable n) { return new ConsComparableList(n, this); }
  /** Inserts n in proper order in this ComparableList, assuming this is sorted in ascending order. */
  abstract ComparableList insert(Comparable n);
}

class EmptyComparableList extends ComparableList {
  static EmptyComparableList ONLY = new EmptyComparableList();
  private EmptyComparableList() { }
  ComparableList sort() { return this; }
  ComparableList insert(Comparable n) { return cons(n); }
}

class ConsComparableList extends ComparableList {
  /** The first element of this. */
  Comparable first;
  /** The remaining elements of this. */
  ComparableList rest;
  ComparableList sort() { return rest.sort().insert(first); }
  ComparableList insert(Comparable n) {
    if (n.compareTo(first) <= 0) return cons(n);
    else return rest.insert(n).cons(first);
  }
}