/**
 * SORTED
 * @author weiss
 */
class IntArrayList
{
    public IntArrayList( )
    {
        items = new int[ 0 ];
    }

    public void add( int x )
    {
        if( theSize == items.length )
            ensureCapacity( theSize * 2 + 1 );

        // Fix add
        int p = 0;

        // Step 1: find first item >= p
        while( p < theSize && items[ p ] < x )
            p++;

        // INVARIANT: items[ p ] >= x (negative of while condition)

        // Step 2: check if x already there (don't want duplicates)
        if( p != theSize && items[ p ] == x )
            return;

        // Step 3: Slide items over
        for( int i = theSize - 1; i >= p; i-- )
            items[ i + 1 ] = items[ i ];

        // Step 4: Place x
        items[ p ] = x;

        // Step 5:
        theSize++;
    }

    public void ensureCapacity( int cap )
    {
        if( cap < theSize )
            throw new IllegalArgumentException( );

        int [ ] old = items;

        items = new int[ cap ];

        for( int i = 0; i < theSize; i++ )
            items[ i ] = old[ i ];
    }

    /**
     * @param x the item to remove (NOT THE INDEX)
     * @return whether the remove was successful
     */
    public boolean remove( int x )
    {
        int p = 0;

        // Step 1: find first item >= p
        while( p < theSize && items[ p ] < x )
            p++;

        // Not found
        if( p == theSize || items[ p ] != x )
            return false;

        // Found
        for( int i = p + 1; i < theSize; i++ )
            items[ i - 1 ] = items[ i ];

        theSize--;
        return true;
    }
    public void removeIdx( int p )
    {
        if( p < 0 || p >= theSize )
            throw new ArrayIndexOutOfBoundsException( );

        for( int i = p + 1; i < theSize; i++ )
            items[ i - 1 ] = items[ i ];

        theSize--;
    }

    public boolean contains( int x )
    {
        for( int p = 0; p < theSize; p++ )
            if( items[ p ] == x )
                return true;

        return false;
    }

    public int size( )
    {
        return theSize;
    }

    public boolean isEmpty( )
    {
        return size( ) == 0;
    }

    public String toString( )
    {
        String result = "[ ";

        for( int i = 0; i < theSize; i++ )
            result += items[ i ] + " ";

        result += "]";

        return result;
    }

    private int [ ] items;
    private int theSize;
}

public class Day27
{
    public static void main( String [ ] args )
    {
        IntArrayList arr = new IntArrayList( );

        arr.add( 8 );
        arr.add( 4 );
        arr.add( 1 );
        arr.add( 6 );
        arr.add( 12 );
        arr.add( 3 );

        System.out.println( arr );
        arr.remove( 12 );
        System.out.println( arr );
        System.out.println( arr.size( ) );
    }

}