A split of an integer array is good if:


	The array is split into three non-empty contiguous subarrays - named left, mid, right respectively from left to right.
	The sum of the elements in left is less than or equal to the sum of the elements in mid, and the sum of the elements in mid is less than or equal to the sum of the elements in right.


Given nums, an array of non-negative integers, return the number of good ways to split nums. As the number may be too large, return it modulo 109 + 7.

&nbsp;
Example 1:

Input: nums = [1,1,1]
Output: 1
Explanation: The only good way to split nums is [1] [1] [1].

Example 2:

Input: nums = [1,2,2,2,5,0]
Output: 3
Explanation: There are three good ways of splitting nums:
[1] [2] [2,2,5,0]
[1] [2,2] [2,5,0]
[1,2] [2,2] [5,0]


Example 3:

Input: nums = [3,2,1]
Output: 0
Explanation: There is no good way to split nums.

&nbsp;
Constraints:


	3 &lt;= nums.length &lt;= 105
	0 &lt;= nums[i] &lt;= 104

class Solution:
    def waysToSplit(self, nums: List[int]) -> int:
        prefix = [0]
        for x in nums: prefix.append(prefix[-1] + x)
        
        ans = 0
        for i in range(1, len(nums)): 
            j = bisect_left(prefix, 2*prefix[i])
            k = bisect_right(prefix, (prefix[i] + prefix[-1])//2)
            ans += max(0, min(len(nums), k) - max(i+1, j))
        return ans % 1_000_000_007
class Solution {
    public int waysToSplit(int[] nums) {
        int size = nums.length;
        for (int i = 1; i < size; ++i) {
            nums[i] += nums[i - 1];
        }
        int res = 0;
        int mod = 1_000_000_007;
        for (int i = 0; i < size - 2; ++i) {
            int left = searchLeft(nums, i, size - 1);
            int right = searchRight(nums, i, size - 1);
            if (left == -1 || right == -1) {
                continue;
            }
            res = (res + right - left + 1) % mod;
        }
        return res;
    }
    
    private int searchLeft(int[] nums, int left, int right) {
        int pos = -1;
        int min = nums[left];
        int lo = left + 1, hi = right - 1;
        while (lo <= hi) {
            int mi = lo + (hi - lo) / 2;
            int mid = nums[mi] - min;
            int max = nums[right] - nums[mi];
            if (mid < min) {
                lo = mi + 1;
            } else if (max < mid){
                hi = mi - 1;
            } else {
                pos = mi;
                hi = mi - 1;
            }
        }
        return pos;
    }
    
    private int searchRight(int[] nums, int left, int right) {
        int pos = -1;
        int min = nums[left];
        int lo = left + 1, hi = right - 1;
        while (lo <= hi) {
            int mi = lo + (hi - lo) / 2;
            int mid = nums[mi] - min;
            int max = nums[right] - nums[mi];
            if (mid < min) {
                lo = mi + 1;
            } else if (max < mid){
                hi = mi - 1;
            } else {
                pos = mi;
                lo = mi + 1;
            }
        }
        return pos;
    }
    
}
class Solution {
public:
    int waysToSplit(vector<int>& nums) {
        int n = nums.size(), mod = 1e9 + 7;  long long ans = 0;
        vector<int> prefix(n);
        partial_sum(nums.begin(), nums.end(),prefix.begin());
        for (int i = 0; i < n - 2; i++) {
            int left = prefix[i], remain = (prefix[n - 1] - prefix[i]);
                if (remain < left * 2) break;
            int leftPtr = lower_bound(prefix.begin() + i + 1, prefix.end() - 1, left * 2) - prefix.begin();
            int rightPtr = upper_bound(prefix.begin() + i + 1, prefix.end() - 1, left + remain / 2) - prefix.begin() - 1;

            if (rightPtr - leftPtr + 1 > 0) ans += rightPtr - leftPtr + 1;
        }
        
        return ans % mod;
    }
};
var waysToSplit = function(nums) {
    const mod = 1000000007;
    const lastIndex = nums.length - 2;
    const total = nums.reduce((sum, num) => sum + num)

    let midLeftPtr = -1;
    let midRightPtr = -1;
    
    let leftSum = 0;
    let midLeftSum = 0;
    let midRightSum = 0;
    
    let numWaysToSplit = 0;
    
    for (let leftPtr = 0; leftPtr < nums.length; leftPtr++) {
        leftSum += nums[leftPtr];        
        midLeftSum -= nums[leftPtr];
        midRightSum -= nums[leftPtr];

       // find the first index that satisfies the middle sum
	   // being greater than or equal to the left sum
        while (midLeftPtr <= lastIndex && 
               (midLeftPtr <= leftPtr || midLeftSum < leftSum)) {
            midLeftPtr++;
            midLeftSum += nums[midLeftPtr]
        }

        // find the first index that makes the middle sum greater than the right sum
        while (midRightPtr <= lastIndex && 
               (midLeftPtr > midRightPtr || midRightSum <= total - midRightSum - leftSum)) {
            midRightPtr++
            midRightSum += nums[midRightPtr]
        }
        numWaysToSplit = (numWaysToSplit + midRightPtr - midLeftPtr) % mod;
    }
    return numWaysToSplit
};
Ways to Split Array Into Three Subarrays