public class ArrayVector {
  private Object[] a;		// Array storing the elements of the vector
  private int capacity = 16;	// Length of array a
  private int size = 0;		// Number of elements stored in the vector
  // Constructor
  public ArrayVector() { a = new Object[capacity]; }	// O(1) time
  // Accessor methods
  public Object elemAtRank(int r) { return a[r]; }	// O(1) time
  public int size() { return size; }
  public boolean isEmpty() { return size() == 0; }	// O(1) time
  // Modifier methods
  public Object replaceAtRank(int r, Object e) {	// O(1) time
    Object temp = a[r];
    a[r] = e;
    return temp;
  }
  public Object removeAtRank(int r) {			// O(n) time
    Object temp = a[r];
    for (int i=r; i<size-1; i++)	// Shift elements down
      a[i] = a[i+1];
    size--;
    return temp;
  }
  public void insertAtRank(int r, Object e) {		// O(n) time
    if (size == capacity) {		// An overflow
      capacity *= 2;
      Object[] b = new Object[capacity];
      for (int i=0; i<size; i++) 
	b[i] = a[i];
      a = b;
    }
    for (int i=size-1; i>=r; i--)	// Shift elements up
      a[i+1] = a[i];
    a[r] = e;
    size++;
  }
}