class RandomizedSet:

    def __init__(self):
        self.value_map = {}
        self.values = []
        self.free_idxes = set()

    def insert(self, val: int) -> bool:
        if val in self.value_map:
            return False

        if self.free_idxes:
            idx = self.free_idxes.pop()
        else:
            idx = len(self.values)
            self.values.append(None)
        self.value_map[val] = idx
        self.values[idx] = val
        return True

    def remove(self, val: int) -> bool:
        if val not in self.value_map:
            return False

        idx = self.value_map[val]
        del self.value_map[val]
        self.values[idx] = None
        self.free_idxes.add(idx)

        if len(self.values) < len(self.free_idxes) * 2:
            self.reindex()

        return True

    def reindex(self) -> None:
        idx = 0
        for val in self.value_map.keys():
            self.values[idx] = val
            self.value_map[val] = idx
            idx += 1

        self.free_idxes = set()
        del self.values[idx:]

    def getRandom(self) -> int:
        while True:
            idx = random.randint(0, len(self.values) - 1)
            if self.values[idx] is not None:
                return self.values[idx]


# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()