var empty struct{} = struct{}{}

type RandomizedSet struct {
	set map[int]struct{}
	key []int
}

/** Initialize your data structure here. */
func Constructor() RandomizedSet {
	return RandomizedSet{
		set: make(map[int]struct{}),
	}
}

/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
func (this *RandomizedSet) Insert(val int) bool {
	if _, ok := this.set[val]; ok {
		return false
	}
	this.set[val] = empty
	this.key = append(this.key, val)
	return true
}

/** Removes a value from the set. Returns true if the set contained the specified element. */
func (this *RandomizedSet) Remove(val int) bool {
	if _, ok := this.set[val]; ok {
		delete(this.set, val)
		if n := len(this.set); 2*n < len(this.key) {
			this.key = make([]int, n)
			i := 0
			for k := range this.set {
				this.key[i] = k
				i++
			}
		}
		return true
	}
	return false
}

/** Get a random element from the set. */
func (this *RandomizedSet) GetRandom() int {
	for {
		val := this.key[rand.Intn(len(this.key))]
		if _, ok := this.set[val]; ok {
			return val
		}
	}
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Insert(val);
 * param_2 := obj.Remove(val);
 * param_3 := obj.GetRandom();
 */