import java.util.ArrayList;
public class SortedWordList extends ArrayList<String>
{
  public SortedWordList()
  {
    super();
  }
  public SortedWordList(int size)
  {
    super(size);
  }
  public boolean contains(Object elem)
  {
    String find = "" + elem;
    int left = 0, right = size(), middle;
    while(left <= right)
    {
      middle = (left + right) / 2;
      if(this.get(middle).equals(find))
        return true;
      else if( this.get(middle).compareTo(find) < 0)
        right = middle;
      else
        left = middle;
    }
    return false;
  }
  public int indexOf(Object elem)
  {
    String find = "" + elem;
    int left = 0, right = size(), middle;
    while(left <= right)
    {
      middle = (left + right) / 2;
      if(this.get(middle).equals(find))
        return middle;
      else if( this.get(middle).compareTo(find) < 0)
        right = middle;
      else
        left = middle;
    }
    return -1;
  }
  public String set(int i, String word)
  {
    if( i < 0 || i > size()-1)
      return null;
    String temp = get(i);
    if((i == 0 && this.get(i+1).compareTo(word) > 0) ||
       (this.get(i-1).compareTo(word) < 0 && 
       this.get(i+1).compareTo(word) > 0))
      super.set(i, word);
    else
      throw new IllegalArgumentException("word=" + word + " i=" + i);
    return temp;
  }
  public void add(int i, String word)
  {
    if( i < 0 || i > size()-1)
      return;
    if((i == 0 && this.get(i).compareTo(word) > 0) ||
       (this.get(i-1).compareTo(word) < 0 && 
       this.get(i).compareTo(word) > 0))
      super.add(i, word);
    else
    {
      //this is in the wrong place. i misread part 5 and put it here. too lazy to fix. lol
      int left = 0, right = size(), middle;
      while(left <= right)
      {
        middle = (left + right) / 2;
        if(this.get(middle-1).compareTo(word) < 0 && 
                this.get(middle+1).compareTo(word) > 0)
          super.add(middle, word);
        else if(this.get(middle).compareTo(word) < 0)
          left = middle;
        else if(this.get(middle).compareTo(word) > 0)
          right = middle;
        else
          return;
      }
    }
  }
}