import java.io.*;

public abstract class List {
  int length = 0;
  public abstract String toString();
  public static List fromString(String str) throws IOException {
    StreamTokenizer st = new StreamTokenizer(new StringReader(str));
    st.resetSyntax(); // Let's keep it simple
    st.whitespaceChars(' ', ' '); // Space is the only whitespace
    st.parseNumbers(); // We want numbers
    return fromStringTokenizer(st);
  }
  private static List fromStringTokenizer(StreamTokenizer st) throws IOException {
    switch (st.nextToken()) {
      case StreamTokenizer.TT_EOF:
        return new Empty();
      case StreamTokenizer.TT_NUMBER:
        return new Cons((int) st.nval, fromStringTokenizer(st));
      default:
        throw new IOException("Bad input string");
    }
  }
  public abstract int getFirst();
  public abstract List getRest();
  public abstract int sum();
  public abstract int length();
  public abstract boolean find(int n);
  public abstract List clone();
  public abstract List mapSquare();
  public boolean isIncreasing() {
    return isIncreasing_startingAt(Integer.MIN_VALUE);
  }
  abstract protected boolean isIncreasing_startingAt(int prev);
  public abstract List append(List e2);
  public abstract List firstn(int n);
  public abstract List dropn(int n);
  public List mergesort() {
    int length = this.length();
    if (length < 2)
      return this;
    List e1 = firstn(length/2);
    List e2 = dropn(length/2);
    return e1.mergesort().merge(e2.mergesort());
  }
  public abstract List merge(List e2);
  
  public abstract boolean linearSearch( int item );
  public abstract boolean binarySearch( int item );
  public abstract List    insertionSort( );
}

class Empty extends List {
  public String toString() {
    return "<Empty>";
  }
 
  public int getFirst() { return Integer.MIN_VALUE; }
  public List getRest() { return this; }
  
  public int sum() {
    return 0;
  }
  public int length() {
    return 0;
  }
  public boolean find(int n) {
    return false;
  }
  public List clone() {
    return new Empty();
  }
  public List mapSquare() {
    return new Empty();
  }
  public boolean isIncreasing_startingAt(int prev) {
    return true;
  }
  public List append(List e2) {
    return e2;
  }
  public List firstn(int n) {
    if (n == 0)
      return new Empty();
    else
      throw new IllegalArgumentException();
  }
  public List dropn(int n) {
    if (n == 0)
      return this;
    else
      throw new IllegalArgumentException();
  }
  public List merge(List e2) {
    return e2;
  }
  
  public boolean linearSearch( int item ) {
    return false;
  }
  public boolean binarySearch( int item ) {
    return false;
  }
  public List insertionSort( ) {
    return this;
  }
}

class Cons extends List {
  int first;
  List rest; // not null
  
  public Cons(int first, List rest) {
    this.first = first;
    this.rest = rest;
    this.length = 1 + rest.length;
  }
  
  public String toString() {
    return "(" + first + " " + rest.toString() + ")";
  }
  
  public int getFirst() { 
    return first;
  }
  public List getRest() {
    return rest;
  }
  public int sum() {
    return first + rest.sum();
  }
  public int length() {
    return 1 + rest.length();
  }
  public boolean find(int n) {
    return first == n || rest.find(n);
  }
  public List clone() {
    return new Cons(first, rest.clone());
  }
  public List mapSquare() {
    return new Cons(first * first, rest.mapSquare());
  }
  public boolean isIncreasing_startingAt(int prev) {
    return prev <= first && rest.isIncreasing_startingAt(first);
  }
  public List append(List e2) {
    return new Cons(first, rest.append(e2));
  }
  public List firstn(int n) {
    if (n == 0)
      return new Empty();
    else
      return new Cons(first, rest.firstn(n-1));
  }
  public List dropn(int n) {
    if (n == 0)
      return this;
    else
      return rest.dropn(n-1);
  }
  public List merge(List e2) {
    if (e2 instanceof Empty) {
      return this;
    } else {
      if (first < ((Cons)e2).first)
        return new Cons(first, rest.merge(e2));
      else
        return new Cons(((Cons)e2).first, this.merge(((Cons)e2).rest));
    }
  }
  
  // Assumes the list is sorted in increasing order!
  public boolean linearSearch( int item ) {
    if( item == first )       return true;
    if( item < first )        return false;
    return rest.linearSearch( item );
  }
  
  // Assumes the list is sorted in increasing order.
  public boolean binarySearch( int item ) {
     if( length == 1 )
       return( first == item );
     int pivot = dropn( length/2 ).getFirst();
     if( item < pivot )
       return firstn( length/2 ).binarySearch( item );
     else
       return dropn( length/2 ).binarySearch( item );
  }
  
  public List insertionSort( ) {
     List sorted = new Empty();
     List l      = this;
     while( !( l instanceof Empty ) ) {
       sorted = insert( l.getFirst(), sorted );
       l = l.getRest();
     }
     return sorted;
  }
  
  List insert( int item, List s ) {
     if( s instanceof Empty )       return new Cons( item, s );
     if( item < s.getFirst() )      return new Cons( item, s );
     else return new Cons( s.getFirst(), insert( item, s.getRest() ) );
  }
}