class SortedNames {

  private String[] names; 
  private int count;

  private static final int DEFAULT_MAXIMUM_NAMES = 10;


  public class NameNotFoundException extends Exception {
    public NameNotFoundException (String msg) {
      super (msg);
    }
  }


  public SortedNames (int maximumNames) {
    names = new String[maximumNames];
    count = 0;
  }


  public SortedNames () {
    names = new String[DEFAULT_MAXIMUM_NAMES];
    count = 0;
  }

  
  private void grow() {
    String[] biggerArray = new String[2*names.length];

    for (int index=0; index < names.length; index++) {
      biggerArray[index] = names[index];
    }

    names = biggerArray;
  }


  private void swap (int x, int y) {
    String temp;

    temp = names[x];
    names[x] = names[y];
    names[y] = temp;
  }


  public void insert (String name) {

    if (count == names.length) {
      grow();
    }

/*
    names[count++] = name;

    for (int index=(count-1); (index > 0); index--) {
      int difference = names[index].compareTo(names[index-1]);

      if (difference <=0)
        break;

      swap(index, index-1);
    }
*/

    int index = count;
    while ((index>0) && (names[index-1].compareTo(name)) > 0) { 
      names[index] = names[index-1];
      names[index-1] = null;
    }

    names[index] = name;
    count++;
  }


  public void removeNth(int n) {
    names[n] = null;
    for (int index=n; index < (count-1); index++) {
      names[index] = names[index+1];
      names[index+1] = null;
    }

    count--;
  }


  public int binarySearch (String name) throws NameNotFoundException {
    int left = 0;
    int right = names.length-1;
    int pivot = (left + (right-left)/2);

    while (right>= left) {
      int difference = names[pivot].compareTo(name); 

      if (pivot == 0) return pivot;

      if (difference > 0) {
        right = pivot-1;
      }

      if (difference < 0) {
        left = pivot+1;
      }

      pivot = (left + (right-left)/2);
    }

    throw new NameNotFoundException ("Couldn't find " +name+ " in the array.");
  }

  
  public void removeName (String name) throws NameNotFoundException {
    int index = binarySearch (name);
    removeNth (index);
    
  }

  
  public SortedNames getGreaterThanForward (String name) {
    SortedNames bigNames = new SortedNames(names.length);

    for (int index=0; index < count; index++) {
      if (names[index].compareTo(name) > 0) {
        bigNames.insert (names[index]);
      }
    }

    return bigNames;
  }

  
  public SortedNames getGreaterThanReverse (String name) {
    SortedNames bigNames = new SortedNames(names.length);

    for (int index=(count-1); index >= 0; index--) {
      if (names[index].compareTo(name) > 0) {
        bigNames.insert (names[index]);
      }
    }

    return bigNames;
  }


  private int getIndexNear (String name) {
    int left = 0;
    int right = count-1;
    int pivot = left + (right-left)/2;

    while (right>=left) {
      int difference = names[pivot].compareTo(name);

      if (difference == 0)
        return pivot;

      if (difference > 0) {
        right = pivot-1;
      }

      if (difference < 0) {
        left = pivot+1;
      }

      pivot = left + (right-left)/2; 

    }

    return pivot;
  }


  public SortedNames getGreaterThanBinary (String name) {
    SortedNames bigNames = new SortedNames(names.length);

    int goodStartingPlace = getIndexNear (name);

    for (int index=goodStartingPlace; index < count; index++) {
      if (names[index].compareTo(name) > 0) {
        bigNames.insert (names[index]);
      }
    }

    return bigNames;
  }

    public String toString(){
	String retString = "";
        for(int i = 0;i<names.length;i++)
            if(names[i] != null)
	      retString += "\n" + names[i];
	return retString;
    }

}