Given an integer array nums, partition it into two (contiguous) subarrays left and right so that:


	Every element in left is less than or equal to every element in right.
	left and right are non-empty.
	left has the smallest possible size.


Return the length of left after such a partitioning.

Test cases are generated such that partitioning exists.

&nbsp;
Example 1:

Input: nums = [5,0,3,8,6]
Output: 3
Explanation: left = [5,0,3], right = [8,6]


Example 2:

Input: nums = [1,1,1,0,6,12]
Output: 4
Explanation: left = [1,1,1,0], right = [6,12]


&nbsp;
Constraints:


	2 &lt;= nums.length &lt;= 105
	0 &lt;= nums[i] &lt;= 106
	There is at least one valid answer for the given input.


class Solution:
    def partitionDisjoint(self, nums: List[int]) -> int:
        prefix = [nums[0] for _ in range(len(nums))]
        suffix = [nums[-1] for _ in range(len(nums))]
        for i in range(1, len(nums)):
            prefix[i] = max(prefix[i-1], nums[i-1])
        for i in range(len(nums)-2, -1, -1):
            suffix[i] = min(suffix[i+1], nums[i+1])
        for i in range(0, len(nums)-1):
            if prefix[i] <= suffix[i]:
                return i+1
class Solution {
    public int partitionDisjoint(int[] nums) {
        int mts = nums[0]; // max till scan
        int mtp = nums[0]; // max till partition
        int idx = 0;
        
        for(int i=1; i<nums.length; i++) {
            int val = nums[i];
            if(val < mtp) {
                idx = i;
                mtp = mts;
            }
            
            mts = Math.max(mts, val);
        }
        
        return idx + 1;
    }
}
class Solution {
public:
    vector<int> tree;
    void build(vector<int> &nums) {
        int n=nums.size();
        for(int i=0 ; i<nums.size(); i++) tree[i+n]=nums[i];
        for(int i=n-1 ; i>0 ; i--) tree[i] = min(tree[i<<1],tree[i<<1|1]);
    }

    int query(int l, int r, int n) {
        l+=n,r+=n;
        int ans = INT_MAX;
        while(l<r) {
            if(l&1) ans = min(ans,tree[l++]);
            if(r&1) ans = min(ans,tree[--r]);
            l>>=1; r>>=1;
        }
        return ans;
    }

    int partitionDisjoint(vector<int>& nums) {
        int n=nums.size();
        int mx=-1 ;
        tree.resize(2*n,INT_MAX); build(nums);
        for(int left=0; left<n ; left++) {
            mx = max(mx,nums[left]);
            if(query(left+1,n,n) >= mx) return left+1;
        }
        return n;
    }
};
/**
 * @param {number[]} nums
 * @return {number}
 */
var partitionDisjoint = function(nums) {
    let n = nums.length;
    let leftMax = Array(n).fill(0), rightMin = Array(n).fill(0);
    let left = 0, right = n- 1;
    
    for(let i = 0, j = n - 1;i<n, j>=0 ;i++,j--){
        leftMax[i] = Math.max(nums[i], !i ? -Infinity : leftMax[i-1]);
        rightMin[j] = Math.min(nums[j], j === n - 1 ? Infinity : rightMin[j+1]);
    }
    
    for(let i = 0;i<n-1;i++){
        if(leftMax[i] <= rightMin[i+1]){
            return i + 1;
        }
    }
 
};
Partition Array into Disjoint Intervals