type Solution struct {
	sum []int
	l   int
	n   int
}

func Constructor(w []int) (sol Solution) {
	n := len(w)
	sol.sum = make([]int, n+1)
	for i := range w {
		sol.sum[i+1] = sol.sum[i] + w[i]
	}
	sol.n, sol.l = sol.sum[n], n+1
	return
}

func (this *Solution) PickIndex() int {
	idx := rand.Intn(this.n) + 1
	beg, end := 1, this.l-1
	for beg <= end {
		mid := beg + (end - beg)
		if val := this.sum[mid]; val == idx {
			return mid - 1
		} else if val < idx {
			beg = mid + 1
		} else {
			end = mid - 1
		}
	}
	return beg - 1
}

/**
 * Your Solution object will be instantiated and called as such:
 * obj := Constructor(w);
 * param_1 := obj.PickIndex();
 */