import java.util.AbstractSet;
import java.util.Set;
import java.util.Iterator;

public class IntSparseSet extends AbstractSet<Integer> {
    private int[] sparse, dense;
    private int n, low, high;
    public IntSparseSet(int low, int high) {
        this.low = low;
        this.high = high;
        sparse = new int[high-low];
        dense = new int[high-low];
 	for(int i=0;i<high-low;i++)
        {
            sparse[i]=0;
            dense[i]=0;
        }
        n = 0;
    }
     public boolean is(Integer x){
	if (low<=x && x<high) return true;
	else return false;
    }
     public boolean contains(Object x) {
	if (low<=(Integer)x && (Integer)x<high){
		if (sparse[(Integer)x-low]<n && dense[sparse[(Integer)x-low]]==(Integer)x) return true;
        	else return false;
	}
        else return false;
    }
    public boolean add(Integer x) {
        if (low<=x && x<high && sparse[x-low]< n && dense[sparse[x-low]]==x || (low>x || x>=high)) return false;
        dense[n] = x;
        sparse[x-low] = n;
        n++;
        return true;
    }

    public boolean remove(Object x) {
        if (!this.contains((Integer)x)) return false;
        n--;
        dense[sparse[(Integer)x-low]] = dense[n];
        sparse[dense[n]-low] = sparse[(Integer)x-low];
        return true;
    }
    public void clear() {
        n=0;
    }
    public int size() {
        return n;
    }

    public Iterator<Integer> iterator() {
        Iterator<Integer> it = new Iterator<Integer>() {
            private int i=0;
	    private int l=0;
            public boolean hasNext() {
                if (i< n) return true;
                else return false;
            }

            public Integer next() {
                return dense[i++]+l;
            }
            public void remove() {
                int x = dense[i-1]+l;
                n--;
                dense[sparse[x-low]] = dense[n];
                sparse[dense[n]-low] = sparse[x-low];
            }
        };
        return it;
    }
}