/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
    static class RandomSet<E> extends AbstractSet<E> {

        List<E> dta = new ArrayList<E>();
        Map<E, Integer> idx = new HashMap<E, Integer>();

        public RandomSet() {
        }

        public RandomSet(Collection<E> items) {
            for (E item : items) {
                idx.put(item, dta.size());
                dta.add(item);
            }
        }

        @Override
        public boolean add(E item) {
            if (idx.containsKey(item)) {
                return false;
            }
            idx.put(item, dta.size());
            dta.add(item);
            return true;
        }

        /**
         * Override element at position <code>id</code> with last element.
         * @param id
         */
        public E removeAt(int id) {
            if (id >= dta.size()) {
                return null;
            }
            E res = dta.get(id);
            idx.remove(res);
            E last = dta.remove(dta.size() - 1);
            // skip filling the hole if last is removed
            if (id < dta.size()) {
                idx.put(last, id);
                dta.set(id, last);
            }
            return res;
        }

        @Override
        public boolean remove(Object item) {
            @SuppressWarnings(value = "element-type-mismatch")
            Integer id = idx.get(item);
            if (id == null) {
                return false;
            }
            removeAt(id);
            return true;
        }

        public E get(int i) {
            return dta.get(i);
        }

        public E pollRandom(Random rnd) {
            if (dta.isEmpty()) {
                return null;
            }
            int id = rnd.nextInt(dta.size());
            return removeAt(id);
        }

        @Override
        public int size() {
            return dta.size();
        }

        @Override
        public Iterator<E> iterator() {
            return dta.iterator();
        }
    }
    public static void main (String[] args) throws java.lang.Exception
    {
        RandomSet<Integer> rs = new RandomSet<Integer>();
        for (int i = 0; i < 20; ++i) {
            rs.add(i);
        }

        int count = 50;

        Random r = new Random();

        for (int i = 0; i < count; i++) {
            System.out.println(rs.pollRandom(r));
            rs.remove(i);
            rs.add(i + 20);
        }
    }
}