/** Data Definition: IntList :=  new Empty() + new Cons(int, IntList) */

interface IntList {
}

interface OrdList extends IntList {
  OrdList empty();
  OrdList insert();
}

class Empty implements OrdList {

  static Empty ONLY = new Empty(); // singleton pattern

  /* constructor */
  private Empty() {} 

  /* OrdList methods */

  public OrdList empty() { return Empty.ONLY; }
  public OrdList insert(int i) { return OrdCons(i); }

  /** returns String representation of Empty */
  public String toString() { return "()"; }

  /** returns String representation of Empty without enclosing parens */
  String toStringHelp() { return ""; }
}

class Cons implements IntList {

  private int first;
  private IntList rest;

  /* constructor */
  Cons(int f, IntList r) {
    first = f;
    rest = r;
  }

  /* accessors */

  /** returns first element of non-empty list */
  abstract int getFirst();    

  /** returns all but the first element of non-empty list */
  IntList getRest() { return rest; }
 
  public String toString() {
    // no leading space before first
    return "(" + first + rest.toStringHelp() + ")";
  }
  String toStringHelp() {
    // leading space before each elt 
    return " " + first + rest.toStringHelp();  
  }
}

class OrdCons extends Cons implements OrdList {

  /* Constructors */
  OrdCons(int i, OrdList ol) { super(i, ol); }
  OrdCons(int i) { super(i, Empty.ONLY); }

  /* OrdList methods */
  public OrdList empty() { return Empty.ONLY; }
  public OrdList insert(int i) { 
    if (i <= getFirst()) return new OrdCons(i, this);
    else return new OrdCons(i, ((OrdList) getRest()).insert(i));
  }
}