func numMatchingSubseq(s string, words []string) int {
	ans := 0
	index := [256][]int{}
	for i, c := range s {
		index[c] = append(index[c], i)
	}
	var isSubseq = func(s, word string) bool {
		target := 0
		for _, c := range word {
			if len(index[c]) == 0 {
				return false
			}
			bound := leftBound(index[c], target)
			if bound == -1 {
				return false
			}
			target = index[c][bound] + 1
		}
		return true
	}

	for _, word := range words {
		if isSubseq(s, word) {
			ans += 1
		}
	}
	return ans
}

func leftBound(nums []int, target int) int {
	l, r := 0, len(nums)-1
	for mid := (l + r) / 2; l <= r; mid = (l + r) / 2 {
		if nums[mid] >= target {
			r = mid - 1
		} else {
			l = mid + 1
		}
	}
	if l >= len(nums) {
		return -1
	}
	return l
}

func largestSumOfAverages(nums []int, k int) float64 {
	preSum, n := []int{0}, len(nums)
	for i, v := range nums {
		preSum = append(preSum, preSum[i]+v)
	}
	memo := [101][101]float64{}
	var dfs func(i, k int) float64
	dfs = func(i, k int) float64 {
		if i == n {
			return 0
		} else if k == 1 {
			return float64(preSum[n]-preSum[i]) / float64(n-i)
		} else if memo[i][k] > 0 {
			return memo[i][k]
		}
		ans := 0.0
		for j := i; j < n; j++ {
			t := float64(preSum[j+1]-preSum[i])/float64(j-i+1) + dfs(j+1, k-1)
			if ans < t {
				ans = t
			}
		}
		memo[i][k] = ans
		return ans
	}
	return dfs(0, k)
}

type FreqStack struct {
	maxFreq     int
	valMapFreq  map[int]int
	freqMapVals map[int][]int
}

func Constructor() FreqStack {
	return FreqStack{valMapFreq: map[int]int{}, freqMapVals: map[int][]int{}}
}

func (this *FreqStack) Push(val int) {
	this.valMapFreq[val]++
	this.freqMapVals[this.valMapFreq[val]] = append(this.freqMapVals[this.valMapFreq[val]], val)
	if this.valMapFreq[val] > this.maxFreq {
		this.maxFreq = this.valMapFreq[val]
	}
}

func (this *FreqStack) Pop() int {
	mlen := len(this.freqMapVals[this.maxFreq])
	res := this.freqMapVals[this.maxFreq][mlen-1]
	this.freqMapVals[this.maxFreq] = this.freqMapVals[this.maxFreq][:mlen-1]
	this.valMapFreq[res]--
	if len(this.freqMapVals[this.maxFreq]) == 0 {
		this.maxFreq--
	}
	return res
}

/**
 * Your FreqStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(val);
 * param_2 := obj.Pop();
 */