import java.util.ArrayList; 

public class Sequence extends ArrayList<Integer> {
  public Sequence() {
    this( new int[] { } );  
  }
  public Sequence(int[] values) {
    for (int v : values)
      this.add( v ); 
  }
  public Sequence (Sequence sequence) {
    super( sequence ); // clone  
  }
  // accumulator passing style 
  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 Sequence merge(Sequence a, Sequence b) {
    a = new Sequence( a );  
    b = new Sequence( b );
    if (a.size() == 0) return b;
    else if (b.size() == 0) return a; 
    else { 
      Integer e; 
      if (a.get(0) < b.get(0)) 
        e = a.remove(0); 
      else 
        e = b.remove(0); 
      Sequence result = merge(a, b);
      result.add(0, e); 
      return result; 
    }
  }
  public Sequence mergeSorted(Sequence other) {
    ArrayList<Sequence> p1 = this.split(new Sequence() , this);  
    ArrayList<Sequence> p2 = other.split(new Sequence() , other);  
    return merge(p1.get(0), p2.get(0)); 
  }
  public static void main(String[] args) {    
    Sequence a = new Sequence( new int[] { 4, 5, 9, 3, 1, 7, 6 } ); 
    System.out.println( a ); 
    Sequence b = new Sequence( new int[] { 5, 6, 7, 2, 3 } ); 
    System.out.println( b ); 
    Sequence c = a.mergeSorted(b); 
    System.out.println( c ); 
    
  }
}