import java.util.ArrayList; 

public class Sequence extends ArrayList<Integer> {
  public Sequence(int[] values) {
    for (int v : values)
      this.add( v ); 
  }
  public Sequence (Sequence sequence) {
    super( sequence ); // clone  
  }
  public ArrayList<Sequence> split( Sequence prefix, 
                                    Sequence rest // assume non empty input
                                  ){
    prefix = new Sequence(prefix); // basic clone(s) 
    rest = new Sequence(rest); // emulate C211 
    if (prefix.size() == 0 || 
        prefix.get(prefix.size()-1) < rest.get(0)) {
      prefix.add( rest.get(0) ); 
      rest.remove( 0 ); 
      return split(prefix, rest); 
    } else {
      ArrayList<Sequence> result = new ArrayList<Sequence>(); 
      result.add(prefix); 
      result.add(rest); 
      return result; 
    }
  }  
  public static void main(String[] args) {    
    Sequence a = new Sequence( new int[] { 4, 5, 9, 3, 1, 7, 6 } ); 
    System.out.println( a ); 
    ArrayList<Sequence> pair = a.split( new Sequence( new int[] { } ), a );
    System.out.println( pair.get(0) ); 
    System.out.println( pair.get(1) ); 
  }
}