class Solution {

    int sum = 0;
    int n = 0;
    int [] sumArr;
    public Solution(int[] w) {
        int i=0;
        n=w.length;
        sumArr = new int[n];
        for(int a:w){
            sum+=a;
            sumArr[i++]=sum;
        }
    }

    public int pickIndex() {

        int rdx = (int) (Math.random()*sum)+1;
        int left = 0;
        int right = n-1;
        while(left<right){
            int mid = left+(right-left)/2;
            if(rdx == sumArr[mid])
                return mid;
            else if(rdx>sumArr[mid])
                left = mid+1;
            else
                right = mid;
        }
        return left;
    }
}

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