import java.io.*;

public abstract class List {
  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 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);
}

class Empty extends List {
  public String toString() {
    return "<Empty>";
  }
  
  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;
  }
}

class Cons extends List {
  int first;
  List rest; // not null
  
  public Cons(int first, List rest) {
    this.first = first;
    this.rest = rest;
  }
  
  public String toString() {
    return "(" + first + " " + rest.toString() + ")";
  }
  
  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));
    }
  }
}