class RandomizedCollection {
        //we will be using hashset instead of arraylist as there are duplicates,so order
        //will get jumbled when we remove and swap elements and we wont have last index
        //in the end of the arraylist
        
        HashMap<Integer,HashSet<Integer>> map ;
        List<Integer> arr;
        Random r;

    public RandomizedCollection() {
        map = new HashMap<>();
        arr = new ArrayList<>();
        r = new Random();
    }
    
    public boolean insert(int val) {
        if(map.containsKey(val)){
            arr.add(val);
            map.get(val).add(arr.size()-1);
            return false;
        } 

        map.put(val , new HashSet<>());
        arr.add(val);
        map.get(val).add(arr.size()-1);
        return true;
    }
    
    public boolean remove(int val) {
        if(map.containsKey(val)==false) return false;

        //get any index of value from the hashset and remove it
        int index = 0;
        for(int idx : map.get(val)){
            index = idx;
            map.get(val).remove(idx);
            break;
        }
        //if hashset becomes empty remove from map
        if(map.get(val).size()==0)
        map.remove(val);

        if(index == arr.size()-1)
        arr.remove(index);

        else{
            int swapped = arr.get(arr.size()-1);

            //swapping and removing in O(1)
            arr.set(index,arr.get(arr.size()-1));
            arr.remove(arr.size()-1);

            //updating swapped values hashset
            map.get(swapped).remove(arr.size());    //removing previous index
            map.get(swapped).add(index);
        }

        return true;
    }
    
    public int getRandom() {
        int ri = r.nextInt(arr.size());  //random index

        return arr.get(ri);
    }
}

/**
 * Your RandomizedCollection object will be instantiated and called as such:
 * RandomizedCollection obj = new RandomizedCollection();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */